Binary Search Implementation in CPP

1. Introduction

Binary Search is an efficient searching algorithm that operates on the principle of divide and conquer. For this algorithm to work correctly, the array or list must be in a sorted order. The primary idea is to repeatedly divide the search interval in half, comparing the desired value with the middle element, and discarding half of the interval based on the comparison.

2. Implementation Steps

1. Find the middle element of the array.

2. If the middle element matches the desired value, return its index.

3. If the desired value is less than the middle element, search in the left half.

4. If the desired value is more than the middle element, search in the right half.

5. Repeat the above steps until the desired value is found or the subarray becomes empty.

3. Implementation in C++ Programming

#include<iostream>
#include<vector>
int binarySearch(const std::vector<int>& arr, int x) {
    int l = 0; // starting index
    int h = arr.size() - 1; // ending index
    while (l <= h) {
        int mid = l + (h - l) / 2; // Compute mid point of array
        // If element is present at the middle
        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) {
            h = mid - 1;
        }
        // Else the element can only be present in right subarray
        else {
            l = mid + 1;
        }
    }
    // If we reach here, then the element is not present in array
    return -1;
}
int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int x = 7;
    int result = binarySearch(arr, x);
    if (result != -1) {
        std::cout << "Element " << x << " is present at index " << result << std::endl;
    } else {
        std::cout << "Element " << x << " is not present in the array." << std::endl;
    }
    return 0;
}

Output:

Element 7 is present at index 6

Explanation:

1. The binarySearch function starts by initializing two indices, l and h, representing the beginning and end of the search interval.

2. Within the loop, it calculates the mid index of the current search interval.

3. It then checks whether the middle element matches the desired value (x). If a match is found, the function immediately returns the index of that element.

4. If the desired value is less than the middle element, the function updates the h index to mid - 1 to continue the search in the left half of the current interval.

5. If the desired value is greater than the middle element, the function updates the l index to mid + 1 to continue the search in the right half of the current interval.

6. If the function completes the loop without finding the value, it returns -1 to indicate that the value is not present in the array.