Implementing Binary Search Algorithm in C++

Introduction

The Binary Search algorithm is an efficient way to find an element in a sorted array or list. By repeatedly dividing the search interval in half, binary search reduces the time complexity to O(log n), making it significantly faster than linear search for large datasets. It works on the principle of divide and conquer, where the array is divided into two halves, and the search is conducted on the half where the element is likely to be.

Objective

The objective of this program is to implement the binary search algorithm in C++. We will create a function that accepts a sorted array and a target value to search for. The program will return the index of the target value if found, otherwise, it will return -1 to indicate the element is not present in the array.

Binary Search Program in C++

#include 
using namespace std;

// Function to perform binary search
int binarySearch(int arr[], int size, int target) {
    int low = 0, high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        // Check if the target is at mid
        if (arr[mid] == target)
            return mid;

        // If target is greater, ignore the left half
        if (arr[mid] < target)
            low = mid + 1;

        // If target is smaller, ignore the right half
        else
            high = mid - 1;
    }

    // Target not found
    return -1;
}

int main() {
    // Test the binary search function
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;

    int result = binarySearch(arr, size, target);

    if (result != -1)
        cout << "Element found at index " << result << endl;
    else
        cout << "Element not found" << endl;

    return 0;
}

Program Explanation

Let’s break down the program structure:

• binarySearch function: This function takes an array, its size, and the target element to search. It uses two pointers, low and high, to represent the current search range in the array. The middle element is calculated and compared with the target. If the middle element is equal to the target, its index is returned. Otherwise, the search continues in the appropriate half (left or right) until the target is found or the search range is exhausted.
• main function: This is where the binary search is tested. We define a sorted array and set a target element to search. The binarySearch function is called, and its result is checked. If the element is found, its index is printed; otherwise, a “not found” message is displayed.

How to Run the Program

To run this C++ program:

1. Install a C++ compiler (such as GCC or Clang) if you haven’t already.
2. Create a new file with a .cpp extension (for example, binary_search.cpp).
3. Copy and paste the above code into your file.
4. Open your terminal or command prompt, navigate to the folder where the file is saved, and compile the program using the following command:

   g++ -o binary_search binary_search.cpp

5. Run the compiled program with the command:

   ./binary_search

The output should display the index of the target element if it is present, or “Element not found” if it isn’t.