Now we have our arrays all sorted, we need to be able to search them as part of U3O1-KK07 – techniques for linear and binary searching . We will do this as a playground based on the Ray Winderlich algorithm club.
Linear Search: Is the simplest way of searching. It just goes through the array, starting at position 0, and checks each to see if it matches. If it doesn’t, it will move to the next position and check.
Check out this visualisation, it is based on a sorted array, but should give you the idea.
This is where it is documented
Have a look in your textbook on page 85, it has a linear search. As you can see it is just a loop that continues until the array is completed. This is not a very elegant solution, but it probably could work. We are going to do it a little differently.
1. Start a new playground and name it Linear Search
2. Declare a new array called “array” and populate it with 1000 integers.
74860,7662,18961,95762,33793,43501,18650,1748,24351,58336,34231,21082,67944,42064,95760,31278,6659,65451,8059,95859,48968,24185,75402,92044,14532,99640,71436,90381,44113,55415,30878,28239,77643,46170,99481,95837,28092,9852,62468,5751,14603,56696,61376,59482,13173,48901,74886,12422,32726,36398,72241,49343,76888,15089,72827,44624,59015,46975,17797,33155,32702,99094,87517,2814,42483,10528,21112,38545,85071,12883,69548,45599,60240,62476,52338,43949,55047,8379,23149,23593,19384,29310,32065,99977,44803,17095,91209,31622,75918,93495,77312,3005,16001,20749,23120,82201,31463,72521,76434,11855,88474,71650,67705,25580,62361,13432,44974,22802,97454,45014,87308,10314,57615,79075,14631,41927,57856,93065,51955,31083,93286,48212,57476,54763,31918,24545,52527,99445,91567,24449,48862,8324,68187,29449,65247,30466,45445,34650,13370,33347,2781,25455,51011,34759,38457,91196,85627,1273,43136,14136,98798,91423,99183,27419,66260,82565,51220,71843,57701,57725,82039,43306,81435,40206,68959,87012,32633,72917,44056,65643,22363,11729,47214,46402,95966,77976,22648,97883,58639,67055,13158,67607,39117,85795,29598,94257,42776,10334,82268,45366,38856,10141,56260,23347,39637,93344,18212,73386,8896,14377,87919,54163,35738,49632,58596,38580,78280,68974,37087,45812,17508,26087,40816,16455,51885,57147,63815,65950,83814,4210,67166,37410,97573,17076,91410,48403,31956,96754,13650,5387,30761,40999,53305,99393,82060,75566,22731,9518,10399,55134,62942,66319,2056,55187,61395,96161,17418,88170,47081,14694,94114,41272,77574,72336,35279,5600,13720,93591,55873,99214,69299,46264,37118,89874,11286,37099,94709,95058,93508,1411,41661,61904,30608,32848,18518,58258,12819,784,76825,18164,49085,95649,33549,80422,75911,90835,94688,25901,4900,74334,67952,69952,73838,32646,3276,86647,12103,42824,28469,44805,45830,56345,40228,15412,992,7121,67560,27209,49342,97113,94347,79785,56764,59691,66097,5651,85113,29248,23637,28152,63173,98507,40505,83404,4932,2897,82056,30088,65050,32058,51209,81644,20861,60912,86411,44508,96009,67779,33806,95061,37595,56518,4625,91409,70759,67137,93440,11889,32727,25313,12932,60313,68980,87175,21661,63772,39221,62808,89435,76886,29450,79095,24040,88324,93017,20615,14369,35320,57317,63358,94116,56111,68024,21872,88249,89654,46052,82317,16709,68088,40201,64836,81562,18095,60389,26627,34817,66889,86068,43793,28082,27250,32041,29598,9505,84538,81537,81239,66962,95782,40700,94608,91890,89560,83338,60611,70110,15273,44522,43955,90858,72402,18348,54202,33104,63504,64960,31725,8216,15977,19532,60606,10850,91412,81212,50156,16707,28197,61406,64110,9121,75856,18280,28641,47523,41671,11769,54320,31493,96808,43183,91152,76288,1061,64268,21360,60288,11221,36542,75725,53360,8496,73498,88107,50105,76320,29455,56240,79826,80347,88412,95944,52273,80184,55622,30691,63629,98239,15586,59163,8269,30033,94716,88003,21368,68006,24683,59668,91151,7715,81719,79677,53149,87939,48381,95859,79882,86935,48924,16025,861,59054,63351,93212,20301,75488,74829,27764,48876,14017,78142,21728,16389,83529,4385,85103,58486,17547,43764,70695,67023,95118,74909,351,37875,74940,42078,37836,77849,96279,68742,95967,22939,15489,38482,51031,58668,51375,61139,43791,81205,46281,12860,38380,80415,64051,78591,21251,93660,14095,78854,59602,77039,30216,74628,90079,30247,58388,89155,36183,67299,25446,45018,15409,68834,86096,68052,46869,53214,38213,22850,99413,94771,48380,21506,19536,45575,819,65044,73691,71838,36193,79879,21886,53051,80759,35921,12628,5678,17777,17590,25214,33544,23596,94137,92103,38405,92933,61169,63069,28523,86600,43495,47672,38933,2335,54865,92666,87086,6527,13974,25309,36721,78210,60530,44420,43844,97019,12605,4703,7115,11660,333,42221,25761,84427,82206,94772,90777,9523,48042,42733,29528,63980,76547,11038,70741,94607,2417,27285,63087,68005,38790,69552,11058,30852,12922,79411,19940,16187,31525,15990,38417,99148,24577,28244,79112,37293,57716,7245,69046,61913,42356,48527,69352,70553,73102,4648,99171,44872,61719,56132,62773,12763,66307,48966,15393,24803,743,25198,3483,31672,23059,62197,40759,16628,22521,49866,90106,31760,83563,36828,18016,54367,61334,44756,86802,68353,59959,68002,56584,7953,34265,9074,39497,56561,23271,36511,4690,33918,25668,5207,93145,45062,94959,90760,19222,49434,73422,34891,87445,64060,24708,87500,26949,34239,23416,38549,47782,48871,84039,8759,81345,30705,58164,52323,15957,92680,88012,40243,5328,80491,45615,10931,20411,35000,44828,6908,58011,61907,3408,58603,65869,55535,16681,28998,23480,47687,57186,32446,61954,95958,29893,3340,42410,58600,14198,34009,34722,13369,43020,1778,54277,29166,39040,52148,24750,99770,61352,89061,20086,20612,68330,79498,92923,44889,69564,64356,31678,49659,66543,37828,17467,69570,77634,21900,53879,17023,93874,24476,69362,81398,48675,18007,27976,2397,14507,35486,47735,89835,76251,32015,85250,45255,1799,64800,83042,45189,7310,42658,35209,51863,18712,47077,94099,42078,86720,85616,95538,77317,72503,790,40462,63065,86899,2244,67486,58941,36995,65457,29422,68240,26206,89595,89333,59153,80322,18387,20382,47168,97857,23785,99772,52121,38452,37006,4661,39928,5657,99706,11429,67927,90533,6889,35948,40614,23496,43673,55332,25831,46909,80060,53913,32702,11928,45625,82406,51742,83506,43140,18803,74913,16683,24944,72673,19270,53511,48936,34794,70132,65272,59650,64358,16319,97889,28592,26403,27377,92723,24606,52345,89381,51017,14880,75973,8355,79168,8072,54875,61264,60380,29760,32194,54333,89439,40287,87369,15233,46894,79163,80502,64303,16030,90631,5772,44095,30737,57181,44320,26274,82637,33129,67309,79851,79361,51526,40756,28133,47300,74097,75572,54234,27938,9612,4656,74079,46193,48419,2423,54893,92848,43547,59189,15303,20446,5435,61412,84377,36305,2626,38470,79344,48924,56256,48645,4001,84927,34452,85040,66350,27772,105,76769,40209,33139,19999,75846,53424,96796,86657,65390,82525,40191,67964,59119,70512,27883,71996,46830,69756,96558,50568,37534,52265,61229,34214,53268,78922,99242,63414,16482,37783,37671,25000,78436,79533,61768,85946,87022,89642
3. Add this function to your code *note, the function should go down the bottom
func linearSearch<T: Equatable>(_ array: [T], _ object: T) -> Int? {
for (index, obj) in array.enumerated() where obj == object {
return index
}
return nil
}
What this code does is use the Equatable which requires any conforming type to implement the equal to operator (==) and the not equal to operator (!=) to compare any two values of that type. In this case the array and the object (value in the array position). As it is using “Generics”, which I will not go into now, this code will work for any array data type.
The second line is a for loop that uses the index of the array to see if 2 values match. If they do, then return the index (the position in the array).
This is great, but we have not actually told the linear search what to actually look for. So we will do it with this line of code below our function we just created
4. Add this line of code
linearSearch(array, 79785)
This calls the linear search function, tells it which array to look up, in this case it is just “array” and then the value we are looking for.
Once done, it will take a couple of seconds to populate, but it should return the index of 311. If you wanted to count them i am sure this would be correct.
Awesome, we now have a linear search done and dusted. You will probably have noted that is reasonably slow. Swift however has an even easier way. It has an in-built linear search function.
5. Try commenting out the code you just put in and use this line of code instead
array.index(of:36995)
You should get the index of 828.
Try with a String array now
Try adding a string array and searching through in a linear search.
We will put a linear search into one of our apps that we make later that is an array populated by .csv or .xml
Binary Search:
Can only be used on an array that is already sorted. It divides the array in half each time a comparison is made. This means it is faster than linear.
There is a worked example in your textbook.
Use the visualisation at https://www.cs.usfca.edu/~galles/visualization/Search.html to see how a binary search works.
Lets try it with our playgrounds again, we will do a basic one to start with
1. Create an array as below
var binaraysearchnum = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
2. Add in the code for binary search. This one is based on the one in your textbook, but there are more than 1 way to do this.
func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
var lowerBound = 0
var upperBound = a.count
while lowerBound < upperBound {
let midIndex = lowerBound + (upperBound - lowerBound) / 2
if a[midIndex] == key {
return midIndex
} else if a[midIndex] > key {
upperBound = midIndex
} else {
lowerBound = midIndex + 1
}
}
return nil
3. Now we just need to call the function like we did previously, but this time we need to give it the key (value we are searching for) and the range of the array. Put this line in:
binarySearch(binaraysearchnum, key: 67, range: 0 ..< binaraysearchnum.count)
You should now have a binary search that is returning the index of where the 67 value is stored, in this case it is at index 18. You will also notice that the playground is pretty nice and tells you how many times each part of the code was executed.
Binary Search Task: I would like you to draw up trace-table that represents what this search is actually doing. It is examinable so a good time to get used to doing them.
Now you will have noted that for binary searches to work the data needs to be sorted. We will do this a little later in the course, but once again Swift is nice enough to have built in functions to do just that. Lets try another binary search that is not sorted.
1. Create a new array called binaryarray and copy the values from below
var binarayarray = [66, 80, 32, 95, 16, 22, 35, 56, 24, 2, 58, 52, 9, 75, 81, 70, 64, 74, 84, 36]
2. As it is a binary search, we need the array sorted, we can do this by putting in this code:
binarayarray = binarayarray.sorted()
Fantastic, we now have our array sorted. You can see it straight away in the playground, if it was an app I would suggest adding this code to see it in the console
print(binarayarray)
3. Now we just need to run the binary search code again. I would like you to have a go at it yourself.
Comments