Data Structures & Algorithms Sep 2, 2023 3 min read

Binary Search

Introduction

Binary Search is a powerful algorithm designed to locate the position of an element within a sorted array. The central principle of Binary Search is to focus on the middle element of the current segment of the array. By comparing the target element with this midpoint, the algorithm can determine whether the desired element is located in the left or right portion of the array.

Important Note

Binary search only works on the sorted array. If they are not sorted, they need to be sorted first.

How binary search works

Consider we are searching for target element 57 inside the sorted array: [12, 24, 32, 45, 57, 68, 80].

Step 1

Set two pointers low and high at the array boundaries. Locate the middle element using mid = low + (high - low) / 2 (which evaluates to index 3, value 45). !Step 1: low=0, high=6, mid=3 Since our target 57 is greater than 45, the element must be in the right half of the array.

Step 2

Shift the low pointer to mid + 1 (index 4) to shrink the search space. Find the new middle element mid = low + (high - low) / 2 (which evaluates to index 5, value 68). !Step 2: low=4, high=6, mid=5 Since our target 57 is less than 68, the element must be in the left sub-portion.

Step 3

Shift the high pointer to mid - 1 (index 4). Re-evaluate the new midpoint. Now, low, high, and mid all meet at index 4. !Step 3: low=4, high=4, mid=4 Since arr[mid] is equal to our target 57, the search terminates successfully, returning index 4.

Time complexities

1. Time complexity

Best - O(1)
Average - O(log n)
Worst - O(log n)

2. Space complexity

O(1)

Code

We can write the code for binary search using two methods: 1. Iterative method 2. Recursive method

// Iterative approach
int binarySearch(const vector<int>& arr, int ele) {
    int n = arr.size();
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == ele) {
            return mid; // Element found, return its index
        } else if (arr[mid] < ele) {
            // Target is in the right half
            low = mid + 1;
        } else {
            // Target is in the left half
            high = mid - 1;
        }
    }
    // Element not present in the array
    return -1;
}

// Recursive approach
int binarySearch(const vector<int>& arr, int low, int high, int ele) {
    if (low > high) {
        return -1; // Base case: Search space is empty
    }
    int mid = low + (high - low) / 2;
    if (arr[mid] == ele) {
        return mid; // Element found
    } else if (ele < arr[mid]) {
        // Search in the left sub-array
        return binarySearch(arr, low, mid - 1, ele);
    } else {
        // Search in the right sub-array
        return binarySearch(arr, mid + 1, high, ele);
    }
}

Shreyansh Jain.

404