Home » Technical Interview Questions » Array Interview Questions » Find Element Using Binary Search in Sorted Array

Find Element Using Binary Search in Sorted Array


Given a sorted array, Find element using binary search in the sorted array. If present, print the index of that element else print -1.

Example

Input

arr[] =  {1, 6, 7, 8, 9, 12, 14, 16, 26, 29, 36, 37, 156}

X = 6 //element to be searched

Output

element found at index 1

Approach for Find Element Using Binary Search in Sorted Array

Given a sorted array A with N elements, Searching for an element X with Low and High variables pointing to the starting and end of an array. Now, we check the conditions and maintaining low and high. Once we hit the condition in which low is greater than high then terminate the loop. Binary search reduces the size of the array by half that’s why it leads us to logn time complexity.

Algorithm

1. Till Low is less than or equal to high

a. Set Mid to the Low + (High – Low)/2
b. If the element at the Mid index is equal to the searched element, return Mid
c. If the element at the Mid index is less than the searched element, than we need to search on the right array, so update Low = Mid + 1
d. If the element at the Mid index is greater than the searched element, than we need to search on the left array, so update High = Mid – 1

READ  Maximum Array from Two given Arrays Keeping Order Same

This is an iterative procedure that keeps track of the search boundaries via two variables (Low and High).

C++ Program for Find Element Using Binary Search in Sorted Array

#include <bits/stdc++.h>
using namespace std;
int Binary_search(int arr[] , int X, int low ,int high)
{
  
  while(low <= high) // till low is less than high i.e. there is atleast one integer in the considered part of array
  {
    
    int mid = low + (high - low)/2; //compute the middle index
    
    if(arr[mid] == X) //if equal then return
      return mid;
      
    else if ( arr[mid] < X) //if smaller then increase the lower limit
      low = mid + 1;
      
    else //if larger then decrease the upper limit
    high = mid - 1;
  }
  return -1;
}
int main()
{
  int N,X;
  cin>>N>>X;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  int index = Binary_search(arr,X,0,N-1); //search for the element
  if(index >= 0)
    cout<<index<<endl;
  else
    cout<<-1<<endl;
  return 0;
}
6 7
2 4 5 7 19
3

Complexity Analysis for Find Element Using Binary Search in Sorted Array

Time Complexity

O(Logn) where n id the size of the array. Here we fixed the start and end pointer and at every time and if first>end then stop the loop.

Space Complexity

O(1) because we don’t use any auxiliary space here.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup