sreejithmvarma.in

PCCST303 · Module 4: Sorting and Searching

Binary Search

Linear search checks every element, O(n). If the array is sorted, there's a much faster option: binary search, the same divide-and-halve idea already seen in BST search.

Idea

Definition

Binary search repeatedly compares the target (KEY) against the middle element of the current search range. If they match, done. If KEY is smaller, the entire right half (everything >= the middle) is discarded; if larger, the entire left half is discarded. This halves the search range with every comparison.

Binary search requires the array to be sorted. Applying it to unsorted data gives meaningless results, since the "discard half" logic assumes everything smaller than the middle is to its left and everything larger is to its right, which is only true in a sorted array.

Algorithm

BINARY_SEARCH(A, N, KEY)
// A is the sorted array to search
// N is the number of elements in A
// KEY is the value being searched for
 
1. LOW = 0
2. HIGH = N-1
3. While LOW <= HIGH:
       MID = (LOW + HIGH) / 2      (integer division)
       If A[MID] == KEY:
           Return MID
       Else if KEY < A[MID]:
           HIGH = MID - 1
       Else:
           LOW = MID + 1
4. Return NOT FOUND

Worked example

Searching for 60 in the sorted array [10, 20, 30, 40, 50, 60, 70, 80]:

Index
10
20
30
40
50
60
70
80
01234567
↑LOW
↑HIGH

MID = (0+7)/2 = 3. A[3] = 40. 60 > 40, discard the left half, LOW = 4:

Index
10
20
30
40
50
60
70
80
01234567
↑LOW
↑HIGH

MID = (4+7)/2 = 5. A[5] = 60. 60 == 60, found. Return index 5.

Index
10
20
30
40
50
60
70
80
01234567

Only 2 comparisons were needed to find the target among 8 elements, compared to up to 8 comparisons a linear search might need.

A search that fails

Searching for 45 in the same array:

Index
10
20
30
40
50
60
70
80
01234567
↑LOW
↑HIGH

MID = 3. A[3] = 40. 45 > 40, LOW = 4.

Index
10
20
30
40
50
60
70
80
01234567
↑LOW
↑HIGH

MID = (4+7)/2 = 5. A[5] = 60. 45 < 60, HIGH = 4.

Index
10
20
30
40
50
60
70
80
01234567
↑LOW / HIGH

MID = (4+4)/2 = 4. A[4] = 50. 45 < 50, HIGH = 3. Now LOW (4) > HIGH (3), so the loop ends:

Index
10
20
30
40
50
60
70
80
01234567
↑HIGH
↑LOW

This correctly returns NOT FOUND, since 45 is not in the array.

Complexity

Key Idea

Each comparison eliminates half the remaining candidates. Starting from n elements, after k comparisons at most n / 2ᵏ candidates remain, so the search ends once n / 2ᵏ <= 1, giving k = log₂ n.

CaseComplexity
Best (target at the middle)O(1)
AverageO(log n)
WorstO(log n)
Space (iterative)O(1)
Space (recursive)O(log n), from the call stack
FeatureLinear searchBinary search
Requires sorted dataNoYes
Time complexityO(n)O(log n)
Works on linked listsYes (natural fit)Poorly (no O(1) middle access)
1000 elements, worst case~1000 comparisons~10 comparisons
Binary search needs O(1) access to the middle element by index, which arrays provide but linked lists don't (finding the middle of a linked list means walking half of it). This is why binary search is essentially never used directly on a plain linked list, even though the array version is dramatically faster than linear search.

Quick recall

  • Requires a sorted array. Compares the target against the middle element and discards the half that can't contain it, repeatedly.
  • O(log n) time, since every comparison halves the remaining search space.
  • O(1) extra space iteratively (O(log n) if implemented recursively, via the call stack).
  • Needs O(1) indexed access to the middle, which is why it's an array technique, not a natural fit for linked lists.