Java Code for Binary Search using array example

                        Binary Search searches the specified value (key) in a sorted array (Ascending) and returns the position. Let us see how the Binary Search algorithm works. In this search algorithm, the key is compared with the middle element of the array. If it matches, then the key is found at the middle of the array. If the key is less than the middle element, then the key should be found at left side of the middle element. If the key is greater than the middle element, then the  key should be found at the right side of the middle element. The search continues on either lower half or upper half  of the array.

Consider an array (A) having n elements. Key is the value to be searched. low ->1, high-> n. Now find mid -> (low+high) /2. If Key==A[mid], then position -> mid, if Key<A[mid], then high->mid-1, if Key>A[mid], then low->mid+1, else not found

For Example let us take the numbers  77,33,22,55,34 and find the position of   55 in the list. Sorted list will be 22,33,34,55,77. Middle position is 3 and the  element is 34. Now 55 is compared with 34 and  55 is greater than 34. So the key will be on right side of 34. Now the search continues with elements 55 & 77, and the middle position is 4, now key 55 is compared with 55. Both are equal, so the key is found at 4th position.

In two ways, we can do binary search. One is using the Collections.binarySearch(List list, Object key)   OR We can write our own function as given below

 

Output:

binary search

 

Leave a Reply