Binary Search Algorithm with C++

In this lecture we showed an example of C++ function that implements the Binary Search Algorithm,

With Function

int binary_search(int arr[], int n, int x) {
  int low = 0;
  int high = n - 1;
  int mid;

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

    if (arr[mid] == x) {
      return mid;
    } else if (arr[mid] < x) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}

This function takes an array arr, its size n, and the element x that you want to search for as arguments. It returns the index of x in the array if it is found, or -1 if it is not found.

The function works by repeatedly dividing the search space in half, until the element is found or the search space is empty. This makes the binary search algorithm much faster than a linear search, as it has a time complexity of O(log n) in the worst case.

To use this function, you need to make sure that the array is sorted in ascending order. You can do this using a sorting algorithm such as bubble sort or quick sort.

Without Function

Here is the complete Code with C++

#include<iostream>
using namespace std;

int main()
{
    int Array[]={10,25,30,45,50,65,70};
    int item=70;

    int left,right,middle;
    left=0;
    right=6;


    while(left<=right)
    {
        middle=(left+right)/2;
        if(Array[middle] == item)
        {
            cout<<"The number is pound at index: "<<middle;
        return 0;
        }
        else if(Array[middle] < item)
        {
             left = middle + 1;
        }
        else
        {
             right = middle - 1;
        }
    }
    cout<<"Item is not found in the array"<<endl;

    return 0;
}