ZenCompiler Logo
ZenCompiler
Searching Algorithm

Binary Search Algorithm

Binary Search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, reducing the search space from $N$ to $1$ in $O(\log N)$ time.

Best CaseO(1)
Average CaseO(log N)
Worst CaseO(log N)
Space ComplexityO(1)

Python Implementation

Run & Visualize
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
            
    return -1

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
result = binary_search(numbers, target)
print(f"Element {target} found at index: {result}")

C++ Implementation

Run & Visualize
#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    std::vector<int> nums = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target = 23;
    int idx = binarySearch(nums, target);
    std::cout << "Element " << target << " found at index: " << idx << std::endl;
    return 0;
}

How Binary Search Works

  1. Start with pointers at the beginning (low = 0) and end (high = N - 1) of the sorted array.
  2. Calculate the midpoint: mid = (low + high) // 2.
  3. If the element at arr[mid] equals the target, return mid.
  4. If the target is greater than arr[mid], shift low = mid + 1.
  5. If the target is smaller than arr[mid], shift high = mid - 1.
  6. Repeat until found or until low > high (element not in array).