Binary Search in C++

Yasin Cakal

Binary search is an efficient algorithm for searching large datasets. It is a divide-and-conquer method that works by repeatedly dividing the search interval in half until the desired value is found. It is one of the most used algorithms when it comes to searching for elements in an array, and it is also used in many sorting algorithms. In this article, we will discuss the basics of binary search in C++ and its time and space complexities.

What is Binary Search?

Binary search is a searching algorithm that works by repeatedly dividing the search interval in half until the desired value is found. This algorithm is used to search for an element in a sorted array. It works by comparing the element to be searched with the middle element in the array. If the element is equal to the middle element, then it is found. If not, the search continues in the left or right half of the array depending on the comparison. This process is repeated until the element is found or the search interval is empty.

Working of Binary Search in C++

Binary search in C++ works by repeatedly dividing the search interval in half until the desired value is found. The algorithm begins by setting the lower and upper bounds of the search interval to the first and last elements of the array. The algorithm then compares the element to be searched with the element at the middle of the search interval. If the element is equal to the middle element, then it is found. If not, the search continues in the left or right half of the interval depending on the comparison. This process is repeated until the element is found or the search interval is empty.

Here is an example of a binary search algorithm in C++:

// Returns the index of the element if it is found in the array, else returns -1 
int binarySearch(int arr[], int low, int high, int x) 
{ 
    if (high >= low) 
    { 
        int mid = (low + high)/2; 
  
        // If the element is present at the middle itself 
        if (arr[mid] == x)   
            return mid; 
  
        // If element is smaller than mid, then it can only be present 
        // in left subarray 
        if (arr[mid] > x)  
            return binarySearch(arr, low, mid-1, x); 
  
        // Else the element can only be present in right subarray 
        return binarySearch(arr, mid+1, high, x); 
    } 
  
    // We reach here when element is not present in array 
    return -1; 
}

In the above code, the binarySearch() function takes four parameters: an array of integers, the lower bound of the search interval, the upper bound of the search interval, and the element to be searched. The function then checks if the element is present at the middle of the search interval. If it is, it returns the index of the element. If not, it continues the search in the left or right half of the interval depending on the comparison.

Time and Space Complexity of Binary Search in C++

The time complexity of binary search in C++ is O(log n). This means that the time taken to search for an element in an array increases logarithmically with the size of the array. This makes binary search an efficient algorithm for searching large datasets.

The space complexity of binary search in C++ is O(1). This means that the amount of memory needed to perform the search is fixed and does not depend on the size of the array.

Conclusion

In this article, we discussed binary search in C++ and its time and space complexities. We saw how the algorithm works and how it is used to search for an element in a sorted array. We also saw how the time and space complexities of binary search in C++ are O(log n) and O(1) respectively.

Exercises

Write a C++ program to find the index of a given element using binary search.

#include <iostream>

// Returns the index of the element if it is found in the array, else returns -1 
int binarySearch(int arr[], int low, int high, int x) 
{ 
    if (high >= low) 
    { 
        int mid = (low + high)/2; 
  
        // If the element is present at the middle itself 
        if (arr[mid] == x)   
            return mid; 
  
        // If element is smaller than mid, then it can only be present 
        // in left subarray 
        if (arr[mid] > x)  
            return binarySearch(arr, low, mid-1, x); 
  
        // Else the element can only be present in right subarray 
        return binarySearch(arr, mid+1, high, x); 
    } 
  
    // We reach here when element is not present in array 
    return -1; 
} 

int main() 
{ 
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int x = 8; 
    int index = binarySearch(arr, 0, n-1, x); 
    if (index != -1) 
       std::cout << x << " is present at index: " << index << std::endl; 
    else
       std::cout << x << " is not present in the array" << std::endl; 
    return 0; 
}

Write a C++ program to sort an array using binary search.

#include <iostream>

// Function to perform binary search 
int binarySearch(int arr[], int low, int high, int x) 
{ 
    if (high >= low) 
    { 
        int mid = (low + high)/2; 
  
        // If the element is present at middle itself 
        if (arr[mid] == x)   
            return mid; 
  
        // If element is smaller than mid, then it can only be present 
        // in left subarray 
        if (arr[mid] > x)  
            return binarySearch(arr, low, mid-1, x); 
  
        // Else the element can only be present in right subarray 
        return binarySearch(arr, mid+1, high, x); 
    } 
  
    // We reach here when element is not present in array 
    return -1; 
} 

// Function to sort an array using binary search 
void sortArray(int arr[], int n) 
{ 
    for (int i=0; i<n-1; i++) 
    { 
        int min_index = i; 
        for (int j=i+1; j<n; j++) 
        { 
            // If the element at min_index is greater than the element at j 
            if (arr[min_index] > arr[j]) 
            { 
                // Update the min_index to j 
                min_index = j; 
            } 
        } 
  
        // Swap the elements at min_index and i 
        int temp = arr[min_index]; 
        arr[min_index] = arr[i]; 
        arr[i] = temp; 
    } 
} 

int main() 
{ 
    int arr[] = {5, 4, 3, 2, 1}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    // Sort the array 
    sortArray(arr, n); 
  
    // Find the index of the given element 
    int x = 4; 
    int index = binarySearch(arr, 0, n-1, x); 
    if (index != -1) 
       std::cout << x << " is present at index: " << index << std::endl; 
    else
       std::cout << x << " is not present in the array" << std::endl; 
    return 0; 
}

Write a C++ program to search for an element using binary search and return the number of comparisons.

#include <iostream>

// Returns the index of the element if it is found in the array, else returns -1 
int binarySearch(int arr[], int low, int high, int x, int &count) 
{ 
    if (high >= low) 
    { 
        int mid = (low + high)/2; 
        count++;
  
        // If the element is present at the middle itself 
        if (arr[mid] == x)   
            return mid; 
  
        // If element is smaller than mid, then it can only be present 
        // in left subarray 
        if (arr[mid] > x)  
            return binarySearch(arr, low, mid-1, x, count); 
  
        // Else the element can only be present in right subarray 
        return binarySearch(arr, mid+1, high, x, count); 
    } 
  
    // We reach here when element is not present in array 
    return -1; 
} 

int main() 
{ 
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int x = 8; 
    int count = 0;
    int index = binarySearch(arr, 0, n-1, x, count); 
    if (index != -1) 
       std::cout << x << " is present at index: " << index << std::endl; 
    else
       std::cout << x << " is not present in the array" << std::endl; 
    std::cout << "Number of comparisons: " << count << std::endl; 
    return 0; 
}

Write a C++ program to search for an element in an array using binary search and return the number of comparisons.

#include <iostream>

// Returns the index of the element if it is found in the array, else returns -1 
int binarySearch(int arr[], int low, int high, int x, int &count) 
{ 
    if (high >= low) 
    { 
        int mid = (low + high)/2; 
        count++;
  
        // If the element is present at the middle itself 
        if (arr[mid] == x)   
            return mid; 
  
        // If element is smaller than mid, then it can only be present 
        // in left subarray 
        if (arr[mid] > x)  
            return binarySearch(arr, low, mid-1, x, count); 
  
        // Else the element can only be present in right subarray 
        return binarySearch(arr, mid+1, high, x, count); 
    } 
  
    // We reach here when element is not present in array 
    return -1; 
} 

int main() 
{ 
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int x = 8; 
    int count = 0;
    int index = binarySearch(arr, 0, n-1, x, count); 
    if (index != -1) 
       std::cout << x << " is present at index: " << index << std::endl; 
    else
       std::cout << x << " is not present in the array" << std::endl; 
    std::cout << "Number of comparisons: " << count << std::endl; 
    return 0; 
}

Write a C++ program to find the number of comparisons needed to search for an element using binary search in an array of size n.

#include <iostream>

// Returns the number of comparisons needed to search for an element using binary search 
int binarySearch(int n) 
{ 
    if (n == 0) 
        return 0; 
    return 1 + binarySearch(n/2); 
} 

int main() 
{ 
    int n = 8; 
    int count = binarySearch(n); 
    std::cout << "Number of comparisons: " << count << std::endl; 
    return 0; 
}

Data Structures and Algorithms with C++

Participants 942