Mastering Binary Search Algorithm in C++

Introduction

Binary search is a fundamental algorithm used to quickly locate an element within a sorted array. It’s a powerful and efficient search technique that drastically reduces the search space with each comparison. In this blog post, we’ll dissect a C++ code example that demonstrates the implementation of the binary search algorithm. We’ll explain the code step by step and provide insights into how binary search works.

Code

#include 
using namespace std;

void binarysearch(int arr[],int s,int size);
void binarysearch(int arr[],int s,int size)
{
    int lower=0,higher=size-1,m;
    while(lower<=higher)
    {
        m=(lower+higher)/2;
        if(s==arr[m])
        {
        cout<<"Search found at index"<<m<<endl; return; } else if(s>arr[m])
            lower=m+1;
        else
            higher=m-1;
    }
    cout<<"Search not found"<<endl;
}
/******************************************/
int main()
{
    int n[5],s,size;
    cout<<"Enter value in array of type int:"<<endl;
    for(int i=0;i<5;i++) { cin>>n[i];
    }
    cout<<"Enter number in Search: "; cin>>s;
    size=sizeof(n)/sizeof(n[0]);
    binarysearch(n,s,size);
    return 0;
}

Understanding the Code

Let’s break down the provided code and understand each segment:

Include and Namespace Declaration:

#include <iostream>
using namespace std;

Here, the necessary header file iostream is included to allow input and output operations. The using namespace std statement enables us to use standard C++ functions and objects without explicitly mentioning the namespace.

Binary Search Function:

void binarysearch(int arr[], int s, int size);
void binarysearch(int arr[], int s, int size) {
    // Implementation of binary search algorithm
}

The code defines a function named binary search that takes three parameters: an integer array arr, an integer s (the element to be searched), and an integer size (the size of the array).

Binary Search Implementation:

int lower = 0, higher = size - 1, m;
while (lower <= higher) {
    m = (lower + higher) / 2;
    if (s == arr[m]) {
        cout << "Search found at index " << m << endl; return; } else if (s > arr[m])
        lower = m + 1;
    else
        higher = m - 1;
}
cout << "Search not found" << endl;

Inside the binary search function, the binary search algorithm is implemented. It works by repeatedly dividing the search interval in half. At each step, it calculates the middle index m between lower and higher, and compares the element at that index (arr[m]) with the target element s. If they match, the index is printed, and the function returns. If the target element is greater than arr[m], the search range is adjusted to the upper half; otherwise, it’s adjusted to the lower half. The loop continues until lower is greater than higher, indicating that the search has been exhausted.

Main Function:

int main() {
    int n[5], s, size;
    // Input array values
    // Input search element
    // Calculate array size
    // Call binarysearch function
    return 0;
}

In the main function, an integer array n of size 5 is declared to hold the input values. The user is prompted to input these values. Additionally, the user is asked to input the search element s. The array size is calculated using the formula size = sizeof(n) / sizeof(n[0]), and the binarysearch function is then called with these inputs.

Conclusion

Binary search is a crucial algorithm for efficiently searching for elements within a sorted array. By repeatedly dividing the search space in half, it drastically reduces the number of comparisons required to find the desired element. The provided C++ code exemplifies the implementation of the binary search algorithm, offering insights into how each step contributes to its effectiveness. As you explore and practice binary search, you’ll be better equipped to tackle various searching scenarios in your coding journey.

FAQs

Q1: What is binary search, and why is it important?

A1: Binary search is an algorithm used to find a specific element in a sorted array. It’s important because it significantly reduces the search space with each comparison, resulting in faster search times compared to linear search.

Q2: What are the key components of the binary search algorithm?

A2: The main components are the lower and higher indices that define the search range, the calculation of the middle index m, and the comparisons between the target element and arr[m] to determine the next search interval.

Q3: Why does the array need to be sorted for binary search to work?

A3: Binary search relies on the property of a sorted array to effectively divide the search space in half. If the array is not sorted, the algorithm won’t be able to make accurate decisions about which half to search in, leading to incorrect results.

Q4: What is the time complexity of binary search?

A4: Binary search has a time complexity of O(log n), where n is the number of elements in the array. This efficiency makes it ideal for large datasets.

Q5: Can binary search be used on unsorted arrays?

A5: No, binary search requires a sorted array. Attempting to use it on an unsorted array will not yield accurate results.