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 element 57.

1. Set two pointers low and high.

   

2. Find the middle element, mid = low + (high - low) / 2

   

3. Set the new low and high. Since element is greater than arr[mid], so we change the position of the low pointer.

   

4. Find the new mid. mid = low + (high - low) / 2

mid == ele, hence we have found the element.

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

Copy

// author - Shreyansh Jain
// Iterative method

#include <bits/stdc++.h>
using namespace std;

// Iterative approach
int binarySearch(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;
        } else if (arr[mid] < ele) {
            // Here element is greater than arr[mid]
            // So, we have to search in the right side.
            low = mid + 1;
        } else {
            // In this case, element is lower than arr[mid]
            // So, we have to search in the left side.        
            high = mid - 1;        
        }
    }
    // In case element is not found, simply return -1
    return -1;
}

int main() {
    // n -> Number of elements.
    int n; cin >> n;    
    vector<int> arr(n);  
    for (int i = 0; i < n; i++) {
        cin >> arr[i];        
    }
    // Sorting in ascending order
    sort(arr.begin(), arr.end());
    int ele;
    // The element to be searched.
    cin >> ele;
    int res = binarySearch(arr, ele);
    if (res == -1) {
        cout << "Number not present" << endl;
    } else {
        cout << "Number present at index"<< res << endl;    
    }
}

Copy

// author - Shreyansh Jain
// Recursive method

#include <bits/stdc++.h>
using namespace std;

int binarySearch(vector<int> arr, int low, int high, int ele) {
    int mid = low + (high - low) / 2;
    if (low > high) {
        return -1;
    }
    if (ele == arr[mid]) {
        return mid;
    } else if (ele < arr[mid]) {
        // it means, we have to search in the left side.
        return binarySearch(arr, low, mid - 1, ele);
    } else {
        // it means, we have to search in the right side.
        return binarySearch(arr, mid + 1, high, ele);
    }
}

int main() {
    int n; cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());
    int ele; cin >> ele; // the element to be searched.
    int res = binarySearch(arr, 0, n - 1, ele);
    if (res == -1) {
        cout << "Number not present" << endl;
    } else {
        cout << "Number present at index"<< res << endl;    
    }
}

Thanks for reading. If you like my post, please consider it upvoting.