Program to search an element in an array using binary search in java

Problem Statement:- Write a program to search an  element in given sorted array and if found return index of element else -1 .

Solution: As the problem says we need to search an element in array in java using binary search algorithm.

This algorithm is more efficient than linear search but having only one restriction that the given array must be sorted . Its having time complexity as O(1) in best case and O(log n) in worst case .

This algorithm works on divide and conquer , it divides the array in two parts based on middle element and search required element in that part discarding the other part every time . 

Steps:- 

• initialize three variables start ,end, mid as start =0,end = array length -1 , mid = (start + end)/2
• start looping array until start <=end 
• compare search element with array[mid] , if equal return true 
• if search element is less than middle element then discard right part and go to left part of array
• if search element is greater than middle element then discard left side of array and go to right part.

private static int searchElementUsingBinarySearch(int[] arr, int searchElem) {
int start=0; int end= arr.length-1;
int mid;
do {
mid = (start+end)/2;
if (searchElem == arr[mid]) return mid;
else if (searchElem < arr[mid]) {
end = mid - 1; // go to left part of array
} else {
start = mid+1; // go to right part of array
}
} while (start <= end);
return -1;
}


Explanation:- 

array - [2,5,6,9,11,14,16,20]   , search element = 16

start = 0, end = 8-1= 7 [as array start from 0]

mid = (0+7)/2 = 3.5 => 3

arr[3] = 9 , 9 is not equal to 16

16 (search elem) >9 (arr[mid]) , so our element exist in right part

so start = mid+1 = 4

will repeat same process until start <= end or arr[mid] = search element

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - --

Time Complexity :- 

Best case :- O(1)  

worst case :- O(log n)

__________________________________________________________

output:- 

binary search java

 You can found the full program on below link - binary search java

Notes :- For the binary search the array must be in sorted order and if array is sorted and circulated then this algorithm will not work then we need to modify our existing algorithm to use modify binary search .

A good example of modified binary search you can find in this program - search element in circulated sorted array .

Thanks .