Binary Search Technique

                                                            Binary Search Technique

Home

Note- Search is a process of finding a value in a list of values. In other words, searching is the process of locating given value position in a list of values.

Binary search algorithm finds given element in a list of elements with O(log n) time complexity where n is total number of elements in the list or array. The binary search algorithm can be used with only sorted list of element. That means, binary search can be used only with list of element which are already arranged in a order. The binary search can not be used for list of element which are in random order. This search process starts comparing of the search element with the middle element in the list. If both are matched, then the result is "element found". Otherwise, we check whether the search element is smaller or larger than the middle element in the list. If the search element is smaller, then we repeat the same process for left sublist of the middle element. If the search element is larger, then we repeat the same process for right sublist of the middle element. We repeat this process until we find the search element in the list or until we left with a sublist of only one element. And if that element also doesn't match with the search element, then the result is "Element not found in the list".

Note- In the sequential search, when we compare against the first item, there are at most 

$n-1$ more items to look through if the first item is not what we are looking for. Instead of searching the list in sequence, a binary search will start by examining the middle item. If that item is the one we are searching for, we are done. If it is not the correct item, we can use the ordered nature of the list to eliminate half of the remaining items. If the item we are searching for is greater than the middle item, we know that the entire lower half of the list as well as the middle item can be eliminated from further consideration. The item, if it is in the list, must be in the upper half.

Binary search is implemented using following steps...

• Step 1: Read the search element from the user
• Step 2: Find the middle element in the sorted list

• Step 3: Compare, the search element with the middle element in the sorted list.
• Step 4: If both are matching, then display "Given element found!!!" and terminate the function
• Step 5: If both are not matching, then check whether the search element is smaller or larger than middle element.
• Step 6: If the search element is smaller than middle element, then repeat steps 2, 3, 4 and 5 for the left sublist of the middle element.
• Step 7: If the search element is larger than middle element, then repeat steps 2, 3, 4 and 5 for the right sublist of the middle element.
• Step 8: Repeat the same process until we find the search element in the list or until sublist contains only one element.
• Step 9: If that element also doesn't match with the search element, then display "Element not found in the list!!!" and terminate the function.

Consider the following list of element and search element...

Program for binary search implement in Java.

public class BinarySearch {

public static void main(String[] args) {

int list[]={10,12,20,32,50,55,65,80,99};

int target=199;

int first=0;

int last=list.length-1;

int mid=(first+last)/2;

int count=0;

while(first<=mid){

if(target==list[mid]){

System.out.println("target found at index"+mid);

count++;

System.out.println("No to iteration"+count);

break;

}

else if(target<list[mid]){

last=mid-1;

}

else

first=mid+1;

mid=(first+last)/2;

}

if(first>last){

System.out.println(mid+"\t"+first);

System.out.println("target not found");

System.out.println(count);

}

}

}

Home