C++ Code For Binary Search Algorithm

5 min read Jul 01, 2024

C++ Code for Binary Search Algorithm

The binary search algorithm is a highly efficient searching technique that works on sorted arrays. It repeatedly divides the search interval in half. The algorithm compares the middle element of the array with the search key. If the key matches, the search is successful. Otherwise, the search continues in either the left half or the right half of the array depending on the comparison result.

Here's a C++ implementation of the binary search algorithm:

#include 

using namespace std;

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

    // If the element is present at the middle itself
    if (arr[mid] == x)
      return mid;

    // If the element is smaller than mid, then it can only be present in left subarray
    if (arr[mid] > x)
      right = mid - 1;

    // Else the element can only be present in right subarray
    else
      left = mid + 1;
  }

  // Element is not present in the array
  return -1;
}

int main() {
  int arr[] = {2, 3, 4, 10, 40};
  int n = sizeof(arr) / sizeof(arr[0]);
  int x = 10;

  int result = binarySearch(arr, 0, n - 1, x);

  if (result == -1)
    cout << "Element is not present in the array";
  else
    cout << "Element is present at index " << result;

  return 0;
}

Explanation:

Function binarySearch:
- Takes the sorted array arr, the left and right indices of the search interval (left and right), and the search key x as input.
- Iterates until the left index becomes greater than the right index.
- Calculates the mid index as the average of left and right.
- Compares arr[mid] with the search key x.
- If arr[mid] is equal to x, the search is successful, and the function returns the mid index.
- If arr[mid] is greater than x, the search continues in the left half by setting right to mid - 1.
- If arr[mid] is smaller than x, the search continues in the right half by setting left to mid + 1.
- If the loop completes without finding the key, the function returns -1, indicating that the element is not present in the array.
main function:
- Creates a sorted array arr and the search key x.
- Calls the binarySearch function with the array, left and right indices, and the search key.
- Prints the result based on the return value of binarySearch.

Advantages of Binary Search:

Efficient: Binary search has a logarithmic time complexity (O(log n)), making it significantly faster than linear search (O(n)) for large datasets.
Widely used: It's a fundamental algorithm used in various applications, including data structures, databases, and search engines.
Simple implementation: The algorithm is easy to understand and implement.

Conclusion:

The binary search algorithm is a powerful and efficient technique for searching elements in a sorted array. Its logarithmic time complexity makes it a highly valuable tool for various applications where fast search is crucial.

C++ Code For Binary Search Algorithm