Arrays - Binary Search
This method is a moire efficient way of searching but only when the sequence of numbers is sorted.
Input
A sequence of $n$ sorted numbers in ascending order and a target number key
.
Method
- Compare
key
with number in the middle. - Then focus on only the first half or the second half, dependant on whether
key
is smaller or greater than the middle number. - Reduce the amount of number to be searched by half.
Example
3 | 7 | 11 | 12 | 15 | 19 | 24 | 33 | 41 | 55 |
---|---|---|---|---|---|---|---|---|---|
24 |
Go for lower if there is no middle. Consistency is key.
19 | 24 | 33 | 41 | 55 | |||||
---|---|---|---|---|---|---|---|---|---|
24 |
19 | 24 | ||||||||
---|---|---|---|---|---|---|---|---|---|
24 |
24 | |||||||||
---|---|---|---|---|---|---|---|---|---|
24 |
Found
If the key
is not in the array you can conclude the number is not there when comparing to the last digit.
Pseudo Code
first = 1
last = n
found = false
while first <= last && found == false do
begin
mid = floor((first + last) / 2)
if A[mid] == key then
found == true
else if A[mid] > key then // these two cases will trip first <= last
last = mid - 1
else A[mid] < key
first = mid + 1
end
if found == true then
output "Found"
else
output "Not Found"
Time Complexity
This search is generally quicker than linear search.
- Best case:
key
is the middle number.- $O(1)$
- Worst case:
- The
key
is not in the list. - At most $\lceil\log n\rceil+1$ comparisons.
- $O(\log n)$
This is as every comparison reduces the amount of numbers by at least half. We are asking: “How many times are we dividing $n$ by 2 to get 1?”
- The