Binary Search in C, C++

Binary search is one of the most popular algorithms which searches a key from a sorted range in logarithmic time complexity. In this article, we have discussed the algorithm, it's time complexity in detail and them, implemented in both C & C++. As a follow up there are several use cases or variations of binary search.
Submitted by Radib Kar, on July 20, 2020

Binary search

The word binary means two. Thus it's evident that the algorithm must have some sort of connection with 2. What's that?

Okay first of all we need a sorted range for the binary search to work. Binary search can't work on any unsorted range.

The idea behind the binary search actually relies on this "sorted" word.

Let's take an example to describe the binary search:

Input range: [ 12, 14 , 18, 22, 45, 67, 99, 107] , key to be searched= 67

The basic steps behind the binary search is to first divide the range into two(that's why binary) half based on a pivot. How will we choose the pivot?

We will pick the mid element as our pivot. To find the mid element simple do mid=(left+right)/2 where left is the start index of the current range and right is end index of the current range.

Now we need to check whether the search key is the same as the pivot element or not. If it's the same then, we are done. We found the key.

If it's not the same then there can be two cases:

  1. key> pivot element:
    In this case, we need to check only the right half of the range. Right half means the elements which are greater than the pivot. This is possible only because the array is sorted. Since the array is sorted it's guaranteed that search key will not appear in the left half as it's greater than the pivot. So we can discard the left half and shrink our range to [pivot index+1, right] for further search.
  2. key< pivot element:
    In this case, we need to check only the left half of the range. Left half means the elements which are less than the pivot. This is possible only because the array is sorted. Since the array is sorted it's guaranteed that search key will not appear in the right half as it's less than the pivot. So we can discard the right half and shrink our range to [left, pivot index-1] for further search.

So every time,

  1. We will find the pivot index=(left+ right)/2.
  2. We will check whether the pivot element is key or not, if it's the key then terminate as the key is found. Otherwise, shrink the range and update left or right as per choices discussed above.
  3. Continue until range collapse down to 0(left>right).

Below is the dry run with the algorithm:

Iteration 1:
Initially the range is [ 12, 14 , 18, 22, 45, 67, 99, 107], key=67
So left=0, right= 7
Pivot index is (0+7)/2=3, so pivot is 22
Now pivot < 67(key)
So we need to search the right half only, hence left=pivot index+1=4
Thus the searching range now: [45, 67, 99 , 107]

Iteration 2:
Now, the range is [45, 67, 99, 107], key=67
So left=4, right= 7
Pivot index is (4+7)/2=5, so pivot is 67
Now pivot == 67(key) so key is found 
Terminate the search and return pivot index

Lets' now check how the algo terminates if key is not there:

---------------------------------
Say the key is now 70
Below is the dry run with the algorithm:

Iteration 1:
Initially the range is [ 12, 14 , 18, 22, 45, 67, 99, 107], key=70
So left=0, right= 7
Pivot index is (0+7)/2=3, so pivot is 22
Now pivot < 70(key)
So we need to search the right half only, hence left=pivot index+1=4
Thus the searching range now: [45, 67, 99 , 107]

Iteration 2:
Now, the range is [45, 67, 99, 107], key=70
So left=4, right= 7
Pivot index is (4+7)/2=5, so pivot is 70
Now pivot < 70 (key)
So we need to search in the right half only, hence left=pivot index+1=6
Thus the range will be : [99, 107]

Iteration 3:
Now, the range is [99, 107], key=70
So left=6, right= 7
Pivot index is (6+7)/2=6, so pivot is 99
Now pivot > 70 (key)
So we need to search in the left half only, hence right=pivot index-1=6
Thus the range will be undefined as left=6 
but right is now 5, thus search terminates here.

Key not found.

Time complexity:

The time complexity of the binary search is of course logarithmic, O(log2n). This is because every time our search range becomes half

So, T(n)=T(n/2)+1 (time for finding pivot)

Using the master theorem you can find T(n) to be Log2n. Also, you can think this as a series of n/2+n/4+n/8+n/16+….+1 which is Log2(n).

Better way to find the pivot index:

We were finding the pivot index like (left+ right)/2. But one thing to notice that (left+ right) has a chance to lead to integer overflow. Hence a better method is to find the pivot index like below:

Pivot index= left+ (right-left)/2

Binary Search Implementation in C (Iterative Implementation)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

//iterative binary search
int binary_search_iterative(int* arr, int key, int n)
{
    int left = 0, right = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

int main()
{
    int n = 8000000;
    int* arr = (int*)(malloc(sizeof(int) * n));

    for (int i = 0; i < n; i++)
        arr[i] = i + 1;

    //key there
    int key = 3115999;
    clock_t tStart1 = clock();
    
    int index = binary_search_iterative(arr, key, n);
    if (index == -1)
        printf("key not found\n");
    else
        printf("%d found at index(0 based): %d\n", key, index);
    
    clock_t tend1 = clock();
    
    printf("Time taken in recursive binary search: %.6fs\n", (double)(tend1 - tStart1) / CLOCKS_PER_SEC);
    
    //key not there
    key = 8000001;
    clock_t tStart2 = clock();
    
    index = binary_search_iterative(arr, key, n);
    if (index == -1)
        printf("key not found\n");
    else
        printf("%d found at index(0 based): %d\n", key, index);
    
    clock_t tend2 = clock();
    
    printf("Time taken in recursive binary search: %.6fs\n", (double)(tend2 - tStart2) / CLOCKS_PER_SEC);

    return 0;
}

Output:

3115999 found at index(0 based): 3115998
Time taken in recursive binary search: 0.000080s
key not found
Time taken in recursive binary search: 0.000011s

Binary Search Implementation in C++ (Iterative Implementation)

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

//iterative binary search
int binary_search_iterative(vector<int> arr, int key)
{
    int left = 0, right = arr.size();

    while (left <= right) {

        int mid = left + (right - left) / 2;
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

int main()
{
    int n = 8000000;

    vector<int> arr(n);

    for (int i = 0; i < n; i++)
        arr[i] = i + 1;

    //key there
    int key = 3115999;
    clock_t tStart1 = clock();

    int index = binary_search_iterative(arr, key);
    if (index == -1)
        cout << key << " not found\n";
    else
        cout << key << " found at index(0 based): " << index << endl;

    clock_t tend1 = clock();

    printf("Time taken in iterative binary search: %.6fs\n", (double)(tend1 - tStart1) / CLOCKS_PER_SEC);

    //key not there

    key = 8000001;
    clock_t tStart2 = clock();

    index = binary_search_iterative(arr, key);
    if (index == -1)
        cout << key << " not found\n";
    else
        cout << key << " found at index(0 based): " << index << endl;

    clock_t tend2 = clock();

    printf("Time taken in iterative binary search: %.6fs\n", (double)(tend2 - tStart2) / CLOCKS_PER_SEC);

    return 0;
}

Output:

3115999 found at index(0 based): 3115998
Time taken in iterative binary search: 0.034050s
8000001 not found
Time taken in iterative binary search: 0.031010s

Binary Search Implementation in C (Recursive Implementation)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

//recursive binary search
int binary_search_recursive(int* arr, int key, int left, int right)
{
    if (left > right)
        return -1;
    srand(time(NULL));

    int mid = left + (right - left) / 2;
    if (arr[mid] == key)
        return mid;
    else if (arr[mid] < key) //right half
        return binary_search_recursive(arr, key, mid + 1, right);
    //else left half
    return binary_search_recursive(arr, key, left, mid - 1);
}

int main()
{
    int n = 8000000;
    int* arr = (int*)(malloc(sizeof(int) * n));

    for (int i = 0; i < n; i++)
        arr[i] = i + 1;

    //key there
    int key = 3115999;
    clock_t tStart1 = clock();
 
    int index = binary_search_recursive(arr, key, 0, n);
    if (index == -1)
        printf("key not found\n");
    else
        printf("%d found at index(0 based): %d\n", key, index);
 
    clock_t tend1 = clock();
 
    printf("Time taken in recursive binary search: %.6fs\n", (double)(tend1 - tStart1) / CLOCKS_PER_SEC);
 
    //key not there
    key = 8000001;
    clock_t tStart2 = clock();
 
    index = binary_search_recursive(arr, key, 0, n);
    if (index == -1)
        printf("key not found\n");
    else
        printf("%d found at index(0 based): %d\n", key, index);
 
    clock_t tend2 = clock();
 
    printf("Time taken in recursive binary search: %.6fs\n", (double)(tend2 - tStart2) / CLOCKS_PER_SEC);

    return 0;
}

Output:

3115999 found at index(0 based): 3115998
Time taken in recursive binary search: 0.000121s
key not found
Time taken in recursive binary search: 0.000063s

Binary Search Implementation in C++ (Recursive Implementation)

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

//recursive binary search
int binary_search_recursive(vector<int> arr, int key, int left, int right)
{
    if (left > right)
        return -1;

    int mid = left + (right - left) / 2;
    if (arr[mid] == key)
        return mid;
    else if (arr[mid] < key) //right half
        return binary_search_recursive(arr, key, mid + 1, right);
    //else left half
    return binary_search_recursive(arr, key, left, mid - 1);
}

int main()
{
    int n = 8000000;
    vector<int> arr(n);

    for (int i = 0; i < n; i++)
        arr[i] = i + 1;

    //key there
    int key = 3115999;
    clock_t tStart1 = clock();
 
    int index = binary_search_recursive(arr, key, 0, n);
    if (index == -1)
        cout << key << " not found\n";
    else
        cout << key << " found at index(0 based): " << index << endl;
 
    clock_t tend1 = clock();
 
    printf("Time taken in recursive binary search: %.6fs\n", (double)(tend1 - tStart1) / CLOCKS_PER_SEC);
 
    //key not there
    key = 8000001;
    clock_t tStart2 = clock();
 
    index = binary_search_recursive(arr, key, 0, n);
    if (index == -1)
        cout << key << " not found\n";
    else
        cout << key << " found at index(0 based): " << index << endl;
 
    clock_t tend2 = clock();
 
    printf("Time taken in recursive binary search: %.6fs\n", (double)(tend2 - tStart2) / CLOCKS_PER_SEC);

    return 0;
}

Output:

3115999 found at index(0 based): 3115998
Time taken in recursive binary search: 0.634202s
8000001 not found
Time taken in recursive binary search: 0.705844s

Variation of binary Search

Binary search has a lot of variation which still sticks to the main idea and time complexity, but there are some modifications.

  1. Meta binary search or One-sided Binary search
  2. Randomized binary search





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.