CSE 142 Computer Programming I Concepts This Lecture Searching an array Linear search Binary search Comparing algorithm performance Linear Binary Search 2000 UW CSE P 1 Searching P 2 Searching Problem Specification Searching looking for something Searching an array is particularly common Goal determine if a particular value is in the array We ll see that more than one algorithm will work P 3 Searching as a Function Let 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 1 P 4 Linear Search The array b the size n and the target x are the parameters of the problem None of the parameters are changed by the function Function outline int search int b int n int x The details of the function depend upon the algorithm used P 5 Algorithm start at the beginning of the array and examine each element until x is found or all elements have been examined int 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 P 6 P 1 Linear Search 3 b 12 5 Linear Search 6 142 21 17 45 b Test search v 8 6 12 5 6 5 6 142 21 17 45 Ran off the end Not found P 7 P 8 Linear Search 3 12 Test search v 8 15 Found It b 3 Can we do better 142 21 17 45 Time needed for linear search is proportional to the size of the array An alternate algorithm Binary search works if the array is sorted 1 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 P 10 yellow pages Note The loop condition is written so b index is not accessed if index n while index n b index x P 9 Why is this true Why does it matter Binary Search Strategy Binary Search Strategy What we want Find split between values larger and smaller than x 0 LR b x More precisely n x 0 b L x R n x Situation while searching 0 b L x R n x Step Look at b L R 2 Move L or R to the middle depending on test P 11 Values in b 0 L x Values in b R n 1 x Values in b L 1 R 1 are unknown P 12 P 2 Binary Search Binary 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 0 b L x R n x 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 0 L R b x x P 13 n P 14 Loop Termination Initialization 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 0 L R else R mid b x x P 15 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 0 L R x x b P 16 n Return 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 0 L R n return L x x P 17 b else return 1 n Binary Search 0 b L 1 17 5 2 3 4 5 3 6 12 21 mid R L mid L mid Test bsearch v 8 3 6 7 45 142 R L 1 R n while L 1 R mid L R 2 if b mid x L mid P 18 else R mid P 3 Binary Search Binary Search 0 b 1 17 5 2 3 4 5 3 6 12 21 6 7 45 142 L mid L mid R mid L Test bsearch v 8 17 0 b R L 1 R n while L 1 R mid L R 2 if b mid x L mid P 19 else R mid L 1 17 5 2 3 4 5 3 6 12 21 L mid Test bsearch v 8 143 6 7 45 142 mid L mid L mid L R L 1 R n while L 1 R mid L R 2 if b mid x L mid P 20 else R mid Binary Search 0 b 1 17 5 R mid R L mid 2 3 4 5 6 3 6 12 21 45 142 Is it worth the trouble 7 R mid R L 1 R n Test bsearch v 8 143 while L 1 R mid L R 2 if b mid x L mid P 21 else R mid How 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 comps 1 2 3 4 5 6 7 8 11 21 Array size 1 2 4 8 16 32 64 128 1 024 P 23 1 048 576 Suppose you had 1000 elements Ordinary search would require maybe 500 comparisons on average Binary search after 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 22 Time for Binary Search Key observation for binary search size of the array n that can be searched with k comparisons n 2k Number of comparisons k as a function of array size n k log2 n This is fundamentally faster than linear search where k n …
View Full Document
Unlocking...