Binary search is an advanced version of a linear search algorithm. Binary search provides a best optimum solution to search for an element.

List of values have to be arranged in ascending order or descending order before applying the Binary search logic. You can use any kind of sorting logic like Bubble sort, Selection sort etc.

## Binary search logic

Let's consider our list has below sorted values and we want to search for an element 45.
{23, 45, 67, 87, 98}

• Get the center element from the array and in this case it is 67.
• Compare center element with the key element i.e.; in this case compare 67 with 45
• Since the center element is grater than the key element, we're sure that the key element is in the first half of the list of elements because the array has already been sorted.
• If the center element is less than the key element, the element is in the second half of the list of elements.
• Consider the list of values as either first half or second half and repeat the above steps until element is found or all the array of elements are checked.

Since the Binary search logic work by splitting the list into two part, this search is named as "Binary search" (Binary means two).

## Binary search algorithm

`START DECLARE n, list, start, end, mid, key, found ACCEPT n ECHO "Please enter elements" ACCEPT n values into an array list ECHO "Please enter element to search" ACCEPT key ASSIGN start = 1; ASSIGN end = list.length; ASSIGN found = false WHILE start <= end LOOP   ASSIGN mid = (start + end) / 2;   IF key < list[mid+1] THEN     end = mid - 1;   ELSE IF key > list[mid+1]     start = mid + 1;   ELSE     ASSIGN found = true     BREAK;    END IF END LOOP IF found = true THEN   ECHO "Element found at position \$mid" ELSE   ECHO "Element not found" END IFEND`

## Binary search Java program

`import java.io.*;/** * This class demonstrates the binary search. * @author SANTHOSH REDDY MANDADI * @version 1.0 * @since 25-September-2012 */public class BinarySearchDemo{  public static void main(String args[]) throws Exception  {    int values[] = new int[5];    int key;    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));    System.out.println("Please enter "+values.length+" values:");     for(int i = 0;i<values.length;i++)    {      values[i] = Integer.parseInt(reader.readLine());    }    System.out.println("Sorting values...");    selectionSort(values);    for(int n:values)    {      System.out.print(n+"\t");    }    System.out.println("\nPlease enter a key element to search:");    key = Integer.parseInt(reader.readLine());    int index = binarySearch(values, key);    if(index == -1)    {      System.out.println("Element not found.");    }    else    {      System.out.println("Element found at position "+(index + 1));    }  }  public static void selectionSort(int[] values)  {    //Iterating the list till the end of the list except last one    for (int i=0; i<values.length-1;i++)     {      //Considering the minumum value is current iteration array element      int min = i;      //Trying to find out the smallest element in the array      for(int j=i+1; j<values.length;j++)      {        if (values[j]<values[min])        {          min = j;        }      }      //If smallest element found other than the current iteration array element, swapping will happen      if (i != min)       {        int swap = values[i];        values[i] = values[min];        values[min] = swap;      }    }  }  public static int binarySearch(int[] values, int key)  {    int start = 0;    int end = values.length;    int mid;    while(start <= end)    {      mid = (start + end) / 2;      if(key < values[mid])      {        end = mid - 1;      }      else if(key > values[mid])      {        start = mid + 1;      }      else      {        return mid;      }    }    return -1;  }}`

Output

`santhosh@linux-mk1n:~/Java> java BinarySearchDemoPlease enter 5 values:1232436578Sorting values...12 32 43 65 78 Please enter a key element to search:43Element found at 2santhosh@linux-mk1n:~/Java> java BinarySearchDemoPlease enter 5 values:1232436578Sorting values...12 32 43 65 78 Please enter a key element to search:32Element found at 1santhosh@linux-mk1n:~/Java> java BinarySearchDemoPlease enter 5 values:1232435423Sorting values...12 23 32 43 54 Please enter a key element to search:23Element found at position 2santhosh@linux-mk1n:~/Java> java BinarySearchDemoPlease enter 5 values:3423154323Sorting values...15 23 23 34 43 Please enter a key element to search:34Element found at position 4`

Please note that you can use the Java API implementation for sorting and searching with binary search. Just checkout java.util.Arrays class and it's methods binarySearch and sort.

If you've sometime, why don't you checkout my other Java programs.