Past exam question: 2076 Baisakh (Back), Q10(a)
Open in the Padhaiko appQuestion
Define binary search with example.
Solution
Definition of Binary Search: Binary search is an efficient divide-and-conquer searching algorithm that locates a target key inside a sorted array A[0..n-1] by repeatedly comparing key with the middle element A[mid]:
- If
A[mid] == key, returnmid. - If
key < A[mid], discard the right half (high = mid - 1). - If
key > A[mid], discard the left half (low = mid + 1).
Time complexity is worst case and best case.
Example Trace: Search for key = 23 in sorted array A = [5, 11, 16, 23, 34, 48, 60] ():
low = 0, high = 6:mid = (0 + 6)/2 = 3.A[3] = 23 == keyFound at index 3 (1 comparison).
(If searching for 16: mid=3 (23 > 16) -> high=2; mid=(0+2)/2=1 (11 < 16) -> low=2; mid=2 (16 == 16) Found at index 2.)
Answer:
Binary search halves a sorted search interval at each comparison in time. On [5, 11, 16, 23, 34, 48, 60], searching for 16 probes indices 3 (23) -> 1 (11) -> 2 (16).