Binary Search

Binary search is a divide and conquer search algorithm that runs on sorted arrays to find a specified value, by dividing the array into half every iteration.

Pseudocode §

Algorithm BinarySearch(A, target): #A is a sorted array
	min ← 1 #In code it would 0
	max ← length of A #len(A) - 1
	While min < max do:
		mid = (min + max)//2
		If A[mid] < target then:
			min = mid + 1
		Else if A[mid] target then:
			max = mid - 1
		Else:
			return mid
	End do
End Algorithm

Proof Of Correctness Via Loop Invariants §

Notice how min and max are always surrounding the target value, for every iteration. This can be used to construct a loop invariant:

Loop Invariant: $A[min]\le target\le A[max]$ for all iterations

• i(0) : min = 1 and max = len(A), therefore min and max enclose the entire array
• i(n): Assume that for each iteration i, the loop invariant holds true i.e. $A[min]\le target\le A[max]\forall i$
• i(n+1): [By Cases]
  • Case 1 ($A[mid]=target$): Trivially proven
  • Case 2 ($A[mid]\ge target$ ): max is now updated to mid - 1, keeping target between min and max
  • Case 3 ($A[mid]\le target$): min is updated to mid + 1, keeping target between min and max
• Therefore, since i(n+1) is true for all cases, and i(0) is true, it can be proven, via induction, that binary search is correct.

Complexity Analysis §

Time Complexity: $O(\log (n))$ §

Every iteration of Binary search reduces the search space of the array by half. Therefore the recurrence relation would be $T(n)=T(\frac{n}{2})+O(1)$

Using Iteration:

$T(2)=T(1)+O(1)$ $T(4)=T(2)+O(1)=T(1)+2O(1)$ $T(8)=T(4)+O(1)=T(2)+3O(1)=T(1)+4O(1)$ $\dots T(n)=T(1)+{\log }_2(n)O(1)$

$=O(\log (n))$