Introduction

Binary search is an efficient lookup technique that operates in $O(\log n)$ time. It follows a divide‑and‑conquer strategy, repeatedly halving the search range. To work correctly, the data must be pre‑sorted.

Binary search locates a target value by first examining the element at the center of the collection. If that element matches the key, its index is returned. If the middle element is greater than the key, the algorithm continues in the left sub‑array; otherwise, it proceeds to the right sub‑array. This divide‑and‑conquer process repeats—either iteratively or recursively—until the search interval becomes empty.

Binary Search Algorithm link

Binary search is an interval‑based lookup technique that narrows the search space to progressively smaller segments. Because it decides where to look next by comparing values, the array must be pre‑sorted.

Algorithm outline:

1. Pick the midpoint of the current segment and compare that value with the search key.
   • If they match, return the midpoint’s index.
2. Not a match? Determine whether the key is smaller or larger than the midpoint value.
3. Choose a side:
   • If the key is larger, continue searching in the sub‑array to the right.
   • If the key is smaller, continue in the sub‑array to the left.
4. Repeat this process — select midpoint, compare, choose half — until the remaining segment is empty.
5. If the key never appears before the segment size reaches zero, report that the search failed (e.g., return $−1$).

Pseudocode link

• Input:
  • $A$ – a sorted array (or list) of $n$ elements.
  • $key$ – the value you want to locate inside $A$.
• Output:
  • If key exists in $A$: the $0$‑based index $i$ such that $A[i] == key$.
  • If key is not present: the value $‑1$, signaling $`` \text{not found}’'$