Table of Contents

## 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

## Complexity Analysis

### 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.