Binary Search Algorithm – A Complete DSA Guide

Binary Search is one of the most important and commonly asked topics in
Data Structures and Algorithms (DSA).
It is widely used in technical interviews and real-world applications
where fast searching is required.

What is Binary Search?

Binary Search is an efficient searching algorithm used to find an element
in a sorted array.
Instead of checking each element one by one (like Linear Search),
Binary Search repeatedly divides the search space into half.

Because of this divide-and-conquer approach, Binary Search is much faster
than Linear Search for large datasets.

Prerequisite for Binary Search

• The array must be sorted (ascending or descending).
• Random access to elements (arrays work best).

How Binary Search Works

1. Find the middle element of the array.
2. Compare the middle element with the target value.
3. If the target equals the middle element, search is successful.
4. If the target is smaller, repeat the search on the left half.
5. If the target is larger, repeat the search on the right half.
6. Continue until the element is found or the range becomes empty.

Binary Search Example

Consider the sorted array:
[2, 5, 8, 12, 16, 23, 38, 56]
and the target value 23.

• Middle element = 12 → target is greater
• Search right half
• Middle element = 23 → element found

Binary Search Time and Space Complexity

• Best Case: O(1)
• Average Case: O(log n)
• Worst Case: O(log n)
• Space Complexity (Iterative): O(1)
• Space Complexity (Recursive): O(log n)

Binary Search Implementation in JavaScript

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    }

    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}
    

Binary Search Implementation in C++

int binarySearch(vector<int>& arr, int target) {
  int left = 0;
  int right = arr.size() - 1;

  while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] == target)
      return mid;

    if (arr[mid] < target)
      left = mid + 1;
    else
      right = mid - 1;
  }

  return -1;
}
    

When to Use Binary Search?

• When data is sorted
• When performance matters
• In large datasets
• In system design and backend optimizations

Common Mistakes in Binary Search

• Applying binary search on an unsorted array
• Incorrect mid calculation causing overflow
• Infinite loops due to wrong boundary updates

Binary Search Interview Questions

• Find first and last occurrence of an element
• Search in rotated sorted array
• Find square root using binary search
• Find minimum element in sorted rotated array

Conclusion

Binary Search is a foundational algorithm in DSA that every developer must master.
Its efficiency, simplicity, and frequent appearance in interviews make it a
must-know topic for beginners and experienced programmers alike.

If you are preparing for coding interviews or improving your problem-solving skills,
mastering Binary Search will give you a strong advantage.