Binary Search

Binary Search

You are given a sorted array of integers and a target, your task is to search for the target in the given array. Assume the given array does not contain any duplicate numbers.

Intuition

We will use a couple of pointers i.e. low and high to apply binary search. Initially, the low pointer should point to the first index and the high pointer should point to the last index.

Search space: The entire area between the low and the high pointer(including them) is considered the search space. Here, the search space is sorted.

Algorithm:

Now, we will apply the binary search algorithm in the given array:

Step 1: Divide the search space into 2 halves:

In order to divide the search space, we need to find the middle point of it. So, we will take a ‘mid’ pointer and do the following:

• mid = (low+high) // 2 ( ‘//’ refers to integer division)

Step 2: Compare the middle element with the target:

In this step, we can observe 3 different cases:

• If arr[mid] == target: We have found the target. From this step, we can return the index of the target possibly.
• If target > arr[mid]: This case signifies our target is located on the right half of the array. So, the next search space will be the right half.
• If target < arr[mid]: This case signifies our target is located on the left half of the array. So, the next search space will be the left half.

Step 3: Trim down the search space:

Based on the probable location of the target we will trim down the search space.

• If the target occurs on the left, we should set the high pointer to mid-1. Thus the left half will be the next search space.
• Similarly, if the target occurs on the right, we should set the low pointer to mid+1. Thus the right half will be the next search space.

The above steps will continue until either we found the target or the search space becomes invalid i.e. high < low. By definition of search space, it will lose its existence if the high pointer is appearing before the low pointer.

Dry-run:

Note: If the target is not present in the array, low and high will cross each other

CODE  

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

int binarySearch(vector<int>& nums, int target) { // Corrected vector declaration
    int n = nums.size(); // Size of the array
    int low = 0, high = n - 1;

    // Perform the steps:
    while (low <= high) {
        int mid = (low + high) / 2;
        if (nums[mid] == target) return mid;
        else if (target > nums[mid]) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    vector<int> a = {3, 4, 6, 7, 9, 12, 16, 17};
    int target = 6;
    int ind = binarySearch(a, target);
    if (ind == -1) 
        cout << "The target is not present." << endl;
    else 
        cout << "The target is at index: " << ind << endl;

    return 0;
}

OUTPUT  

Before In the algorithm, in every step, we are basically dividing the search space into 2 equal halves. This is actually equivalent to dividing the size of the array by 2, every time. After a certain number of divisions, the size will reduce to such an extent that we will not be able to divide that anymore and the process will stop. The number of total divisions will be equal to the time complexity.

Let’s derive the number of divisions mathematically,

If a number n can be divided by 2 for x times:
	2^x = n
Therefore, x = logn (base is 2)
So the overall time complexity is O(logN), where N = size of the given array.