Find Element Using Binary Search in Sorted Array

Problem Statement

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

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

Implementation

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

Java Program for Find Element Using Binary Search in Sorted Array

import java.util.Scanner;
class sum
{
    public static 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;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int x = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int index = Binary_search(a,x,0,n-1); //search for the element
        if(index >= 0)
          System.out.println(index);
        else
          System.out.println(-1);
    }
}

6 7
2 4 5 7 1 9

3