Tuesday, February 4, 2020

Binary Search in Java

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,

  1. Divide the sorted array into three parts( left, middle element, right )
  2. if the search item matches the middle element then return position middle.
  3. if search item is less then middle item search left division of the array by calling the method itself on left division of array.
  4. 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.
  5. 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;
}
}


Video Tutorial