Master Binary Search

Greetings, Fellow Coders!

Welcome to another exciting blog post where we delve into the world of algorithms and problem-solving. Today, we’re going to tackle the classic problem of Binary Search.

Problem Description:

In binary search, we’re given a sorted array of size N and an integer K. The task is to find the position (0-based indexing) at which K is present in the array using binary search.

Let’s illustrate this problem with a couple of examples:

Example 1:

Input:
N = 5
arr[] = {1, 2, 3, 4, 5}
K = 4

Output: 3

In this example, we need to find the position of 4 in the array which is at 3rd index.

Example 2:

Input:
N = 5
arr[] = {14, 24, 33, 35, 51} 
K = 48

Output: -1

Here, we’re looking for the position of 48 in the array which is not present in array, so -1 would be the output.

Solution Approach:

We’ll utilize the binary search algorithm to efficiently find the position of K in the given sorted array. The binary search algorithm works by repeatedly dividing the search interval in half. We maintain two pointers, ‘l’ and ‘r’, representing the left and right boundaries of the search space. At each step, we calculate the mid-point ‘m’, and compare the element at this position with K. Based on this comparison, we adjust the search space accordingly until we find the desired element or exhaust the search space.

Let’s walk through the solution step by step:

• Initialize ‘l’ to 0 and ‘r’ to n – 1, where n is the size of the array.
• While ‘l’ is less than or equal to ‘r’, calculate the mid-point ‘m’.
• If the element at ‘m’ is equal to K, return ‘m’ (position of K).
• If the element at ‘m’ is greater than K, update ‘r’ to m – 1.
• If the element at ‘m’ is less than K, update ‘l’ to m + 1.
• If the loop exits without finding K, return -1 indicating K is not present in the array.

Time Complexity Analysis:

Binary search has a time complexity of O(log N), where N is the size of the array. This is because at each step, the search space is halved.

Now, let’s implement the solution and showcase it with code:

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

class Solution {
public:
    int binarysearch(int arr[], int n, int k) {
        int l = 0;
        int r = n - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            
            if (arr[m] == k)
                return m;
                
            if (arr[m] > k)
                r = m - 1;
            else
                l = m + 1;
        }
        return -1;
    }
};

int main() {
    Solution s;
    
    // Example 1
    int arr1[] = {1, 2, 3, 4, 5};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int k1 = 4;
    cout << "Example 1 Output: " << s.binarysearch(arr1, n1, k1) << endl;
    
    // Example 2
    int arr2[] = {14, 24, 33, 35, 51};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int k2 = 48;
    cout << "Example 2 Output: " << s.binarysearch(arr2, n2, k2) << endl;
    
    return 0;
}

Explanation:

• We define a Solution class with a binarysearch method that takes an array arr, its size n, and the target integer k.
• Inside binarysearch, we initialize two variables l and r representing the left and right pointers of the search interval. l is set to 0, and r is set to n – 1 (the last index of the array).
• We enter a while loop that continues as long as l is less than or equal to r, ensuring there’s still a valid search space.
• Inside the loop, we calculate the mid-point m of the search interval using (l + r) / 2. This avoids overflow issues by using (r – l) / 2 to calculate the mid-point.
• We check if the element at the mid-point arr[m] is equal to the target k. If it is, we return m, indicating we’ve found the target at position m.
• If arr[m] is greater than k, it means the target lies to the left of m. Therefore, we update r to m – 1 to narrow down the search space.
• If arr[m] is less than k, it means the target lies to the right of m. Therefore, we update l to m + 1 to narrow down the search space.
• If the loop exits without finding the target, we return -1 to indicate that the target k is not present in the array.

Now, when we run the code with Example 1:

arr1[] = {1, 2, 3, 4, 5}
n1 = 5
k1 =

The output will be the position of 5 in the array, which is 3 (0-based indexing).

Conclusion:

Binary search is a powerful algorithm used to efficiently search for elements in a sorted array. With a time complexity of O(log N), it’s an excellent choice for scenarios where quick search operations are required. By understanding and implementing this algorithm, you’ve added another valuable tool to your problem-solving arsenal. Keep exploring and happy coding!