Problem:  Given an array of integer write an algorithm to find the element  which is to be searched. Take input from the user and return the index of the element.

int [] arrA = {1,3,5,0,6,9,4,1,2};
Enter the element to be searched :- 5
Output: Element found at index: 3

Naïve approach:-

This approach searches the element by running a outer loop (also called linear search) in O(n) time.

Binary search approach:-

The basic idea behind binary search is that we initially find the mid element of the array and then compare the   element that need to be searched with the mid element.

To perform binary search on a array , the prerequisite condition is that the array need to be sorted.

  The array can be sorted by calling the sort() function defined in  #include<algorithm>.

The sort(int ar) function contains the argument array that need to be sorted.

Steps:-

1: First sort the array :if not sorted call the sort() function by including the headerfile #include<algorithm.h>

Or use any sorting algorithm.

2: Now find the mid element of the array by using the formula :-

Int mid=(low+high)/2     or

Int mid= low + (high-low)/2;

3: Now compare the key which need to be searched with the mid element.

If key id smaller than mid , then mark the high variable as high=mid-1

And if key is greater than mid , mark the low as mid=low+1.

Run the loop until the low<=high.

Code is compiled and run in Turbo c++.

Code:-

#include<iostream.h> 

using namespace std;

int binarySearch(int ar[], int low,int high, int key)

{

    while (low <= high)

    {




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

  

        // check if key is the mid element

        if (arr[mid] == key)

            return mid;

  

        // If key is  greater, ignore left half

        if (arr[mid] < key)

            low = mid + 1;

  

        // If key is smaller, ignore right half

        else

            high = mid - 1;

    }

  

    

    return -1;

}

  

int main()

{

    int n,key;

   cout<<”Enter the size of the array:”;

   cin>>n;

   int ar[n];

   cout<<”Enter the key to search”;

    cin>>key;

    int result = binarySearch(ar, 0, n-1, key);

    (result == -1)? printf("Element is not present"

                                       " in array")

               : printf("Element is present at "

                                "index %d", result);

    return 0;

}

Time Complexity: The time complexity is O(logn) if the array is already sorted.

If the array is not sorted , the time complexity becomes O(nlogn), i.e O(n) for sorting the array.