C++ Binary Search Function

5 min read Jul 01, 2024

C++ Binary Search Function

Binary search is a highly efficient algorithm for finding a specific element within a sorted array. It works by repeatedly dividing the search interval in half. This article will guide you through the implementation of a binary search function in C++.

Understanding the Algorithm

Sorted Array: Binary search requires the input array to be sorted in ascending order.
Divide and Conquer: The algorithm begins by comparing the target value with the middle element of the array.
Three Possibilities:
- Match Found: If the target value matches the middle element, the search is successful.
- Target is Smaller: If the target value is smaller than the middle element, the search continues in the left half of the array.
- Target is Larger: If the target value is larger than the middle element, the search continues in the right half of the array.
Recursive Process: Steps 2 and 3 are repeated recursively on the remaining half until either the target is found or the search interval becomes empty.

C++ Implementation

#include 

using namespace std;

// Function to perform binary search
int binarySearch(int arr[], int left, int right, int target) {
  while (left <= right) {
    int mid = left + (right - left) / 2; // Calculate midpoint

    // Check if the target value is found
    if (arr[mid] == target) {
      return mid;
    }

    // Adjust search interval based on comparison
    if (arr[mid] < target) {
      left = mid + 1; // Target is in the right half
    } else {
      right = mid - 1; // Target is in the left half
    }
  }

  // Target not found
  return -1; 
}

int main() {
  int arr[] = {2, 5, 7, 8, 11, 12};
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 12;

  int index = binarySearch(arr, 0, n - 1, target);

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

  return 0;
}

Explanation

binarySearch function:
- Parameters: Takes the sorted array (arr), left and right indices of the search interval (left, right), and the target value (target).
- Iterative Approach: Uses a while loop to repeatedly divide the interval.
- Midpoint Calculation: Calculates the middle index using mid = left + (right - left) / 2 to avoid integer overflow.
- Target Comparison: Compares the target value with the element at the midpoint.
- Interval Adjustment: Updates the search interval based on the comparison result.
- Return Value: Returns the index of the target if found, otherwise returns -1.
main function:
- Initialization: Defines a sorted array, its size, and the target value.
- Function Call: Calls the binarySearch function to locate the target.
- Output: Prints the result indicating whether the target was found and its index.

Advantages of Binary Search

Time Complexity: Has a logarithmic time complexity of O(log n), making it highly efficient for large datasets.
Efficiency: Significantly faster than linear search, especially for large arrays.
Wide Applicability: Used in various applications like searching in databases, dictionaries, and other sorted data structures.

Conclusion

This article provided a comprehensive understanding of the binary search algorithm and its implementation in C++. By following the principles of divide and conquer, binary search offers a highly efficient solution for searching within sorted arrays.

C++ Binary Search Function