Binary Search

#include <iostream>
using namespace std;

bool binarySearch(int *arr, int s, int e, int k) {

    // Base case: Element not found if the start index (s) becomes greater than the end index (e)
    if(s > e)
        return false;

    // Calculate the middle index of the current array segment
    int mid = s + (e - s) / 2;

    // Base case: Element found, return true if the middle element matches the target (k)
    if(arr[mid] == k)
        return true;

    // If the middle element is smaller than the target, search the right half of the array
    if(arr[mid] < k) {
        return binarySearch(arr, mid + 1, e, k);  // Recursive call for the right half
    }
    // If the middle element is larger than the target, search the left half of the array
    else {
        return binarySearch(arr, s, mid - 1, k);  // Recursive call for the left half
    }
}

Example Walkthrough:

Let’s say we have an array arr = {1, 3, 5, 7, 9} and we want to find the target k = 7 using binarySearch(arr, 0, 4, 7).

1. First Call (s = 0, e = 4):
   • The middle index mid = 2, so arr[mid] = 5. Since 5 < 7, the function recursively searches the right half of the array with binarySearch(arr, 3, 4, 7).
2. Second Call (s = 3, e = 4):
   • The middle index mid = 3, so arr[mid] = 7. Since arr[mid] == k, the function returns true, indicating that the target has been found

Output:

If the element is found, it returns true; otherwise, it returns false.