Example 2
haystack = 1 3 4 5 6 8
needle = 7 We start with l pointing to the leftmost element and r pointing to the rightmost element in the array.
haystack = 1 3 4 5 6 8
^ ^
l r
needle = 7Let’s hide the contents of the haystack for now.
haystack = * * * * * *
^ ^
l r
needle = 7As the number of elements in the segment of interest is even, there is no element directly in the middle. We choose to compare the needle against an element situated just to the left of the middle, which is 4.
v
haystack = 1 3 4 5 6 8 (revealed)
haystack = * * 4 * * * (hidden)
^ ^
l r
needle = 7It is smaller than the needle, and therefore we restrict the segment of interest to the half on the right-hand side.
haystack = * * 4 * * *
^ ^
l r
needle = 7We compare the needle against the element in the middle of the new segment of interest, which is 6.
haystack = * * 4 * 6 *
^ ^
l r
needle = 7
This element is again smaller than the needle, and therefore we restrict the segment of interest to the half on the right-hand side.
haystack = * * 4 * 6 *
^
l=r
needle = 7We now compare the needle against the single element remaining in the segment of interest.
haystack = * * 4 * 6 8
^
l=r
needle = 7It is larger than the needle, and therefore we restrict the segment of interest to the left-hand side.
haystack = * * 4 * 6 8
^
l>r
needle = 7Our segment of interest is now empty, and the needle is therefore not in the haystack.
Check out the next page for a more detailed discussion on the time complexity.
- Page 1 – Introduction
- Page 2 – How It Works – Overview
- Page 3 – Example 1
- Page 4 – Example 2
- Page 5 – Why Binary Search is so Fast
- Page 6 – Implementation
- Page 7 – Conclusion