The binary search algorithm is an efficient way to search for an element in a sorted array. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, the search continues in the lower half. Otherwise, it continues in the upper half. This process continues until the value is found or the interval is empty.

Program Structure

// C++ program to implement binary search algorithm

#include 
using namespace std;

// Function to perform binary search on a sorted array
int binarySearch(int arr[], int size, int target) {
    int left = 0;              // Starting index
    int right = size - 1;     // Ending index

    // Loop until the left index is less than or equal to the right index
    while (left <= right) {
        int mid = left + (right - left) / 2; // Calculate mid index

        // Check if target is present at mid
        if (arr[mid] == target) {
            return mid; // Target found at index mid
        }
        // If target is greater, ignore the left half
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        // If target is smaller, ignore the right half
        else {
            right = mid - 1;
        }
    }
    return -1; // Target not found
}

// Main function
int main() {
    int arr[] = {2, 3, 4, 10, 40}; // Sample sorted array
    int size = sizeof(arr) / sizeof(arr[0]); // Calculate size of the array
    int target = 10; // Target value to search for

    // Perform binary search
    int result = binarySearch(arr, size, target);

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

    return 0; // Indicate successful completion
}

Documentation

• Header Files: #include <iostream> is included for input and output operations.
• Function binarySearch: This function takes a sorted array, its size, and the target value as inputs. It returns the index of the target if found, or -1 if not found.
• Parameters:
  • int arr[]: The sorted array in which to search.
  • int size: The number of elements in the array.
  • int target: The value to search for.
• Local Variables:
  • left: The starting index of the search range.
  • right: The ending index of the search range.
  • mid: The middle index of the current search range.
• Main Function: Initializes a sample sorted array, calls the binarySearch function, and displays the result.

Conclusion

The binary search algorithm is a classic example of an efficient searching technique that operates in O(log n) time complexity. This makes it far superior to linear search for larger datasets. Understanding this algorithm is essential for optimizing search operations in programming.