Arrays - Binary Search

COMP108 Lectures 2021-02-18

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

1. Compare key with number in the middle.
2. Then focus on only the first half or the second half, dependant on whether key is smaller or greater than the middle number.
3. 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?”