Binary Search in C++

Binary search is an efficient algorithm used to search for a specific element in a sorted array. Here’s an example of how to implement binary search in C++:

#include <iostream>
#include <vector>

// Binary search function
int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // Element found; return its index
        } else if (arr[mid] < target) {
            left = mid + 1; // Adjust the left boundary
        } else {
            right = mid - 1; // Adjust the right boundary
        }
    }

    return -1; // Element not found
}

int main() {
    std::vector<int> sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int target = 7;

    int result = binarySearch(sortedArray, target);

    if (result != -1) {
        std::cout << "Element " << target << " found at index " << result << std::endl;
    } else {
        std::cout << "Element " << target << " not found in the array." << std::endl;
    }

    return 0;
}

In this code:

1. We define a binarySearch function that takes a sorted vector arr and a target value target as parameters.
2. We initialize two pointers, left and right, which represent the current search range. Initially, left is set to the beginning of the array (index 0), and right is set to the end of the array (index arr.size() - 1).
3. Inside the while loop, we calculate the middle index (mid) of the current search range.
4. We compare the element at the middle index with the target value:

• If they are equal, we return the index of the element (indicating that the element has been found).
• If the element at the middle index is less than the target, we adjust the left pointer to mid + 1 to search the right half of the current range.
• If the element at the middle index is greater than the target, we adjust the right pointer to mid - 1 to search the left half of the current range.

1. We repeat this process until left is less than or equal to right. If the loop exits without finding the target element, we return -1 to indicate that the element is not in the array.
2. In the main function, we create a sorted vector sortedArray and specify the target value to search for.
3. We call the binarySearch function and display the result, indicating whether the target element was found and at which index.

This binary search algorithm has a time complexity of O(log n), making it efficient for searching in large sorted datasets.