C++ Binary Search Algorithm

5 min read Jul 01, 2024

C++ Binary Search Algorithm

The Binary Search algorithm is a highly efficient search algorithm that is used to find a specific element within a sorted array. It works by repeatedly dividing the search interval in half. This makes it significantly faster than linear search, especially for large arrays.

How Binary Search Works:

Start with the middle element: The algorithm begins by comparing the target value with the middle element of the array.
Divide the search space: If the target value is equal to the middle element, the search is complete. If the target value is less than the middle element, the search continues in the left half of the array. If the target value is greater than the middle element, the search continues in the right half of the array.
Repeat steps 1 and 2: The process of dividing the search space and comparing the target value with the middle element is repeated until the target value is found or the search interval becomes empty.

C++ Implementation:

#include 

using namespace std;

int binarySearch(int arr[], int left, int right, int target) {
  while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] == target) {
      return mid; // Target value found at index mid
    } else if (arr[mid] < target) {
      left = mid + 1; // Search in the right half
    } else {
      right = mid - 1; // Search in the left half
    }
  }

  return -1; // Target value not found
}

int main() {
  int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
  int n = sizeof(arr) / sizeof(arr[0]);
  int target = 23;

  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;
}

Advantages of Binary Search:

Efficient: Binary search has a time complexity of O(log n), making it much faster than linear search, especially for large arrays.
Simple: The algorithm is relatively simple to understand and implement.
Widely applicable: Binary search is widely used in various applications, including searching in databases, finding specific values in sorted data, and implementing efficient data structures.

Disadvantages of Binary Search:

Requires sorted data: Binary search only works on sorted arrays. If the array is not sorted, you need to sort it first before applying binary search.
Limited to specific data structures: Binary search is primarily used for searching in arrays or other linear data structures. It cannot be directly applied to other data structures like trees or graphs.

Conclusion:

The binary search algorithm is a powerful and efficient tool for searching in sorted data. Its logarithmic time complexity makes it significantly faster than linear search, particularly for large datasets. It is widely used in various applications, making it a fundamental algorithm in computer science.

C++ Binary Search Algorithm