Binary Search
Another simple searching technique is binary search, as a sequential search. A binary search can only be applied to a sorted data structure. We can repeatedly divide the data -structure into two parts, and we will keep matching the bounds of arrays with the search key. So, every time the search space will become half. We keep doing this until either the item is found or the entire search space is exhausted.
We can summarise the program to implement a binary search as,
- Divide the sorted array into three parts( left, middle element, right )
- if the search item matches the middle element then return position middle.
- if search item is less then middle item search left division of the array by calling the method itself on left division of array.
- if the search item is greater then item then search the right division of the array by calling the method itself on the right division of the array.
- Otherwise, return not found.
The binary search performs better than a linear search because it uses the information that the list is sorted. The complexity of the binary search is O(log n).
Binary Search Flow Chart
Binary Search Program
import
java.util.Scanner;
public
class
DemoBinarySearch {
public
static
void
main(String[] args) {
int
arr[]= {11,19,23,35,41,46,51,63,89,100,107,115};//Binary Search
DemoBinarySearch
dbs=new DemoBinarySearch();
Scanner
scan=new Scanner(System.in);
System.out.println("Enter
item to search?");
int
r=scan.nextInt();
int
s=dbs.binarySearch(r, arr, 0, arr.length-1);
if(s==-1)
{
System.out.println("not
found");
}
else
{
System.out.println("found
at position"+s);
}
}
public
int
binarySearch(int item,int arr[],int
low,int high)
{
if(high>=low)
{
int
mid=low+(high-low)/2;
if(arr[mid]==item)
{
return
mid;
}
if(arr[mid]>item)//search left
side
{
return
binarySearch(item, arr, low, mid-1);
}
//otherwise search right side
return
binarySearch(item, arr, mid+1, high);
}
return
-1;
}
}