Skip to content
doubtly

1 answer

Binary search divides a sorted array into two halves, compares the key with the middle element, and conquers by searching only the half that can contain the key.

Divide and conquer steps:

  • Divide: find the middle index \(mid = \lfloor(low + high)/2\rfloor\).
  • Conquer: if key == a[mid], the search is successful. If key < a[mid], search the left half \([low, mid-1]\); otherwise search the right half \([mid+1, high]\).
  • Combine: nothing to combine; the answer of the sub-problem is the answer.
  • If \(low > high\), the key is not present.
BinSearch(a, low, high, key):
  if low > high: return -1
  mid = (low + high) / 2
  if key == a[mid]: return mid
  else if key < a[mid]:
      return BinSearch(a, low, mid - 1, key)
  else:
      return BinSearch(a, mid + 1, high, key)

Example: search for 23 in a = [5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0 to 8).

  1. low = 0, high = 8, mid = 4: a[4] = 23 = key. Found at index 4.

Search for 72:

  1. mid = 4, a[4] = 23 < 72, so search right half: low = 5.
  2. low = 5, high = 8, mid = 6: a[6] = 56 < 72, so low = 7.
  3. low = 7, high = 8, mid = 7: a[7] = 72. Found at index 7.

Time complexity: each step halves the problem, so \(T(n) = T(n/2) + c\), which gives \(T(n) = O(\log n)\). Best case \(O(1)\) (key at the middle). The array must be sorted.

Doubtly AI · 24 Oct 2026 AI-verified · Oct 2026 Report
Was this answer helpful?

Your answer

Log in or create a free account to answer this question.