P-1P-1CSE 142Computer Programming ILinear & Binary Search©2000 UW CSEP-2Concepts This LectureSearching an arrayLinear searchBinary searchComparing algorithm performanceP-3SearchingSearching = looking for somethingSearching an array is particularly commonGoal: determine if a particular value is in the arrayWe’ll see that more than one algorithm will workP-4Searching Problem: SpecificationLet b be the array to be searched, n be the size of the array, and x be the value being searched for (the "target")The question is, "Does x occur in b?"If x appears in b[0..n-1], determine its index, i.e., find the k such that b[k]==x. If x not found, return –1P-5Searching as a FunctionThe array b, the size n, and the target x are the parameters of the problem.None of the parameters are changed by the functionFunction outline:int search (int b[ ], int n, int x) {...}The details of the function depend upon the algorithm used.P-6Linear Searchint search (int b[ ], int n, int x) {int index = 0;while (index < n && b[index] != x)index++;if (index < n)return index;else return -1;}Algorithm: start at the beginning of the array and examine each element until x is found, or all elements have been examinedP-2P-7Linear SearchTest:search(v, 8, 6)3 12 -5 6 142 21 -17 45bFound It!P-8Linear SearchTest:search(v, 8, 15)3 12 -5 6 142 21 -17 45bRan off the end! Not found.P-9Linear SearchNote: The loop condition is written so b[index] is not accessed if index>=n.while (index < n && b[index] != x)(Why is this true? Why does it matter?)3 12 -5 6 142 21 -17 45bP-10Can we do better?Time needed for linear search is proportional to the size of the array.An alternate algorithm, "Binary search," works if the array is sorted1. Look for the target in the middle.2. If you don’t find it, you can ignore half of the array, and repeat the process with the other half.Example: Find first page of pizza listings in the yellow pagesP-11Binary Search StrategyWhat we want: Find split between values larger and smaller than x:<= x > x0 L R nb<= x > x?0 L R nbSituation while searchingStep: Look at b[(L+R)/2]. Move L or R to the middle depending on test.P-12Binary Search StrategyMore preciselyValues in b[0..L] <= xValues in b[R..n-1] > xValues in b[L+1..R-1] are unknown<= x > x?0 L R nbP-3P-13Binary Search/* If x appears in b[0..n-1], return its location, i.e.,return k so that b[k]==x. If x not found, return -1 */int bsearch (int b[ ], int n, int x) {int L, R, mid;___________________ ;while ( _______________ ) {}_________________ ;}<= x > x?0 L R nbP-14Binary Search/* If x appears in b[0..n-1], return its location, i.e.,return k so that b[k]==x. If x not found, return -1 */int bsearch (int b[ ], int n, int x) {int L, R, mid;___________________ ;while ( _______________ ) {mid = (L+R) / 2;if (b[mid] <= x)L = mid;else R = mid;}_________________ ;}<= x > x?0 L R nbP-15Loop Termination/* If x appears in b[0..n-1], return its location, i.e.,return k so that b[k]==x. If x not found, return -1 */int bsearch (int b[ ], int n, int x) {int L, R, mid;___________________ ;while ( L+1 != R ) {mid = (L+R) / 2;if (b[mid] <= x)L = mid;else R = mid;}_________________ ;}<= x > x?0 L R nbP-16Initialization/* If x appears in b[0..n-1], return its location, i.e.,return k so that b[k]==x. If x not found, return -1 */int bsearch (int b[ ], int n, int x) {int L, R, mid;L = -1; R = n;while ( L+1 != R ) {mid = (L+R) / 2;if (b[mid] <= x) L = mid;else R = mid;}_________________ ;}<= x > x0 L R nbP-17Return Result/* If x appears in b[0..n-1], return its location, i.e.,return k so that b[k]==x. If x not found, return -1 */int bsearch (int b[ ], int n, int x) {int L, R, mid;L = -1; R = n;while ( L+1 != R ) {mid = (L+R) / 2;if (b[mid] <= x) L = mid;else R = mid;}if (L >= 0 && b[L] == x) return Lelse return -1;}<= x > x0 L R nbP-18Binary SearchTest: bsearch(v,8,3);-17 -5 3 6 12 21 45 142b0 1 2 3 4 5 6 7L RmidL = -1; R = n;while ( L+1 != R ) {mid = (L+R) / 2;if (b[mid] <= x) L = mid;else R = mid;}RmidLmidLP-4P-19Binary SearchTest: bsearch(v,8,17);-17 -5 3 6 12 21 45 142bLRmidL = -1; R = n;while ( L+1 != R ) {mid = (L+R) / 2;if (b[mid] <= x) L = mid;else R = mid;}midmidL RL0 1 2 3 4 5 6 7P-20Binary SearchTest: bsearch(v,8,143);-17 -5 3 6 12 21 45 142bLRmidL = -1; R = n;while ( L+1 != R ) {mid = (L+R) / 2;if (b[mid] <= x) L = mid;else R = mid;}midmidmidL L L L0 1 2 3 4 5 6 7P-21Binary SearchTest: bsearch(v,8,-143);-17 -5 3 6 12 21 45 142bLRmidL = -1; R = n;while ( L+1 != R ) {mid = (L+R) / 2;if (b[mid] <= x) L = mid;else R = mid;}midmidRRR0 1 2 3 4 5 6 7P-22Is it worth the trouble?Suppose you had 1000 elementsOrdinary search would require maybe 500 comparisons on averageBinary searchafter 1st compare, throw away half, leaving 500 elements to be searched.after 2nd compare, throw away half, leaving 250. Then 125, 63, 32, 16, 8, 4, 2, 1 are left.After at most 10 steps, you’re done!What if you had 1,000,000 elements??P-23How Fast Is It?Another way to look at it: How big an array can you search if you examine a given number of array elements?……1,02411……1,048,57621128864732616584432211Array size# compsP-24Time for Binary SearchKey observation: for binary search: size of the array n that can be searched with k comparisons: n ~ 2kNumber of comparisons k as a function of array size n: k ~ log2nThis is fundamentally faster than linear search (where k ~ n)P-5P-25SummaryLinear search and binary search are two different algorithms for searching an arrayBinary search is vastly more efficientBut binary search only works if the array elements are in orderLooking ahead: we will study how to sort arrays, that is, place their elements in
View Full Document
Unlocking...