C++ Program to Implement Binary Search

Binary search is a fundamental algorithm used in computer science to find the position of a target value within a sorted array. The beauty of binary search lies in its efficiency: it repeatedly divides the search interval in half, drastically reducing the number of comparisons needed to locate the target. This article will guide you through the implementation of binary search in C++, using real-world examples to illustrate its practical applications. We will cover the necessary prerequisites, provide detailed explanations of each example, and include the output for each program.

Prerequisites

Before diving into the code, ensure you have a basic understanding of the following concepts:

1. Arrays: A collection of elements stored at contiguous memory locations.
2. Sorting: Binary search requires the array to be sorted. Familiarize yourself with sorting algorithms like Quick Sort or Merge Sort.
3. C++ Syntax: Basic knowledge of C++ programming, including loops, conditional statements, and functions.

1. Introduction to Binary Search

1.1 Definition

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. If the value of the target element is less than the middle element of the interval, the algorithm narrows the interval to the lower half. Otherwise, it narrows it to the upper half. This process continues until the target value is found or the interval is empty.

1.2 Formula

The binary search algorithm can be outlined with the following steps:

1. Start with the middle element of the array.
2. If the target value matches the middle element, return the index.
3. If the target value is less than the middle element, search the left half of the array.
4. If the target value is greater than the middle element, search the right half of the array.
5. Repeat the process until the target value is found or the subarray reduces to zero.

2. Implementation of Binary Search in C++

2.1 Example 1: Binary Search in a Sorted Array of Integers

Let’s start with a basic implementation of binary search in a sorted array of integers.

#include <iostream>
using namespace std;

int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // Element not found
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    int result = binarySearch(arr, size, target);
    
    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }
    
    return 0;
}

Output:

Element found at index 3

2.2 Example 2: Binary Search in a Sorted Array of Strings

Binary search is not limited to integers. It can also be applied to an array of strings.

#include <iostream>
#include <string>
using namespace std;

int binarySearch(string arr[], int size, string target) {
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // Element not found
}

int main() {
    string arr[] = {"apple", "banana", "cherry", "date", "fig", "grape"};
    int size = sizeof(arr) / sizeof(arr[0]);
    string target = "date";
    int result = binarySearch(arr, size, target);
    
    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }
    
    return 0;
}

Output:

Element found at index 3

2.3 Example 3: Recursive Binary Search

Binary search can also be implemented recursively, which can sometimes make the code more intuitive.

#include <iostream>
using namespace std;

int recursiveBinarySearch(int arr[], int left, int right, int target) {
    if (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] < target) {
            return recursiveBinarySearch(arr, mid + 1, right, target);
        } else {
            return recursiveBinarySearch(arr, left, mid - 1, target);
        }
    }
    
    return -1; // Element not found
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    int result = recursiveBinarySearch(arr, 0, size - 1, target);
    
    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found" << endl;
    }
    
    return 0;
}

Output:

Element found at index 4

Conclusion

Binary search is an essential algorithm in computer science, providing an efficient method for finding elements in a sorted array. Its logarithmic time complexity makes it significantly faster than linear search, especially for large datasets.