University of Washington Computer Programming I Lecture 15 Linear Binary Search 2000 UW CSE P 1 Concepts This Lecture Searching an array Linear search Binary search Comparing algorithm performance P 2 Searching 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 Specification Let b be the array to be searched n is the size of the array and b is x is value being search for If x appears in b 0 n 1 return its index i e return k such that b k x If x not found return 1 None of the parameters are changed by the function Function outline int search int b int n int x P 4 Linear Search 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 5 Linear Search b 3 12 5 6 142 21 17 45 Test search v 8 6 Found It P 6 Linear Search b 3 12 5 6 142 21 17 45 Test search v 8 15 Ran off the end Not found P 7 Linear Search b 3 12 5 6 142 21 17 45 Note 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 P 8 Can 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 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 9 yellow pages Binary Search Strategy What we want Find split between values larger and smaller than x 0 LR x b 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 10 Binary Search Strategy More precisely 0 b L x R n x Values in b 0 L x Values in b R n 1 x Values in b L 1 R 1 are unknown P 11 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 P 12 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 mid L R 2 if b mid x L mid else R mid 0 L R b x x P 13 n Loop 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 0 L R b x x P 14 n 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 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 15 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 return L else return 1 0 L R x x b n P 16 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 17 else R mid Binary Search 0 b L 1 17 5 2 3 4 5 3 6 12 21 L mid L mid R mid Test bsearch v 8 17 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 Binary Search 0 b 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 19 else R mid Binary Search 0 b 1 17 5 L mid R mid R 2 3 4 5 6 3 6 12 21 45 142 mid R 7 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 20 else R mid Is it worth the trouble 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 21 comps Array size How Fast Is It 1 1 2 2 Another way to look at it How big an array can you search if you examine a given number of array elements 3 4 4 8 5 16 6 32 7 64 8 128 11 1 024 21 1 048 576 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 P 23 Summary Linear search and binary search are two different algorithms for searching an array Binary search is vastly more efficient But binary search only works if the array elements are in order Looking ahead we will study how to sort arrays …
View Full Document
Unlocking...