Searching Algorithms•Medium

Binary Search

Binary Search Algorithm

Binary Search is an extremely efficient searching algorithm that operates under the Divide and Conquer paradigm. It strictly requires the collection (such as an array) to be sorted beforehand.

How It Works

Instead of checking elements sequentially from left to right, Binary Search jumps directly to the middle element of the current search interval:

  1. Maintain two pointers: low (start of interval) and high (end of interval).
  2. Calculate the middle index: 
    mid = low + (high - low) / 2
  3. Compare the element at mid with the target key:
    • If equal: Return the mid index (Match found!).
    • If key is smaller: The target must lie in the left half. Narrow the interval by moving the high pointer to mid - 1.
    • If key is larger: The target must lie in the right half. Narrow the interval by moving the low pointer to mid + 1.
  4. Repeat steps 2 and 3 as long as low <= high.
  5. If low crosses high and the element was not found, return -1.

Advantages & Disadvantages

Advantages ✅

  • Extremely Fast: Takes logarithmic time O(log N). For an array of 1 million elements, it takes at most 20 comparisons!
  • Low Space Overhead: Operates iteratively in O(1) auxiliary space.

Disadvantages ❌

  • Requires Sorting: The input array must be sorted. Sorting an unsorted array takes O(N log N) time, which outweighs the search speed if done only once.
  • Contiguous Memory: Requires random-access data structures (like arrays) to look up midpoints in O(1) time; does not work efficiently on Linked Lists.

Complexity Analysis

  • Time Complexity:
    • Best Case: O(1) when the target element is located exactly at the middle index on the very first comparison.
    • Average / Worst Case: O(log N) because we reduce the search size by half at each step.
  • Space Complexity: O(1) auxiliary space for the iterative version.