Binary Search In Java

Binary search is a fast search algorithm compared to linear search algorithm. This search algorithm works on the principles of divide and conquer. In  this method requires that the list of elements be in sorted order.

In this method, to search a particular item by comparing the middle most item of the collection. If it matches then the search is successful. Otherwise,the list is divided into two halves,one from 0th element to the center element that means first half and another from center element to the last element that means second half. Binary search always search an element in the sorted array only. If you want search an element an unsorted array then the best technique is Linear Search algorithm already discussed in the previous post. 

As a result,all the elements in first half are smaller than the center element,whereas all the elements in second half are greater than the center element. Since, this method will search an element in the sorted array only. If the element is smaller than the center element then the searching will be done in the first half, otherwise in second half.

The below given is our sorted array and assume that we need to search location of value 33 using binary search.

 Now, we shall determine the half of the array by using this formula:

mid=low+(high-low)/2

Here  low value 0,high value 9 then apply values in the forumal

mid=0+(9-0)/2=4(integer value of 4.5). So 4 is the mid of array.

  Now we compare the value sorted at location 4,with the value being searched i.e.33. But we find that value at location 4 is 28,which is not match. We know that value is greater than 28 which we are searching and we also know that target value must be in the second half of the array.

We change our low  to mid+1 and find the new mid value again.
low=mid+1
mid=low+(high-low)/2

Our new mid is 7 now. We compare the value stored at location 7 with our target value 33

The value stored at location 7 is not match with our target value 33,rather it is less that what we are looking for. So the value must be in lower part from this location.

Now, we calculate mid again,This time it is 5.

Now, we compare the value stored in the location 5 with our target value 33, We find that it is match.

So we conclude that the target value 33 is stored at the location 5.


Algorithm:

Binary Search(a[],ele)
Step 1: Start
Step 2: set i=0,low=0,high=4,flag=1
Step 3: Repeat the steps 4,5,6 & 7 while(i<=4)
Step 4: mid(low+high)/2
Step 5: if(ele==a[mid]) then print mid and flag=0
Step 6: if(ele>a[mid]) then low=mid+1
Step 7: if(ele<a[mid]) then high=mid-1
Step 8: if(flag) then print "given element is not found"
Step 9: Stop

Example:

Search ele =40
Low = 0,high=4
Mid=low+high/2
Mid=2
Ele=a[mid]       (40==30)
Ele>a[mid]       (40>30) then low=mid+1 ------> 2+1=3
Mid=low+high/2----->3+4/2=7/2=3
if(ele==a[mid])  (40==40)

Found position at 3