Binary Search is an efficient searching algorithm used to find an element in a sorted array by repeatedly dividing the search space into half.

Unlike linear search, which checks elements one by one, binary search eliminates half of the remaining elements at each step. This makes it significantly faster for large datasets.

Key Requirement

Binary search can only be applied when the array is already sorted.

The sorting order can be:

  • Ascending order
  • Descending order

If the array is not sorted, binary search will not work correctly.

How Binary Search Works

The algorithm follows these steps:

  • Find the middle element of the array
  • Compare the middle element with the target value
  • If both are equal, the search is complete
  • If the target is smaller, search the left half
  • If the target is larger, search the right half
  • Repeat the process until the element is found or the search space becomes empty

At each step, half of the remaining elements are discarded.

Example Walkthrough

Sorted array:
[10, 20, 30, 40, 50, 60]

Target element:
40

Step-by-step process:

  • Middle element is 30, target is larger, so search the right half
  • New middle element is 50, target is smaller, so search the left half
  • Middle element becomes 40, element found

This demonstrates how binary search reduces the search space efficiently.

Python Example (Text Only)

The iterative binary search approach works as follows:

  • Initialize two pointers named low and high
  • Calculate the middle index
  • Compare the middle element with the target
  • Update the low or high pointer accordingly
  • Continue until the element is found or the range becomes invalid

If the element is found, its index is returned.
If not found, the function returns -1.

Time Complexity

  • Best case: O(1) when the middle element is the target
  • Average case: O(log n)
  • Worst case: O(log n)

Binary search remains efficient even for very large datasets.

Space Complexity

  • Iterative binary search: O(1) because no extra space is used
  • Recursive binary search: O(log n) due to the recursion call stack

Binary search is ideal when:

  • The data is already sorted
  • The dataset is large
  • Fast searching is required
  • Multiple search operations are expected

Binary search should be avoided when:

  • The array is unsorted
  • The dataset is very small
  • Only one search is required and sorting cost is high

Interview Insight

Sorting an unsorted array takes O(n log n) time.

For a single search operation, sorting the array first and then applying binary search is inefficient.

However, when multiple searches are required, sorting once and using binary search multiple times becomes a better approach.

Conclusion

Binary search is one of the most important searching algorithms in computer science.

It provides excellent performance on sorted data and is widely used in real-world systems such as databases, indexing engines, and search services.

Understanding binary search is fundamental for mastering Data Structures and Algorithms.