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 IF
END

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 BinarySearchDemo
Please enter 5 values:
12
32
43
65
78
Sorting values...
12 32 43 65 78 
Please enter a key element to search:
43
Element found at 2

santhosh@linux-mk1n:~/Java> java BinarySearchDemo
Please enter 5 values:
12
32
43
65
78
Sorting values...
12 32 43 65 78 
Please enter a key element to search:
32
Element found at 1

santhosh@linux-mk1n:~/Java> java BinarySearchDemo
Please enter 5 values:
12
32
43
54
23
Sorting values...
12 23 32 43 54 
Please enter a key element to search:
23
Element found at position 2

santhosh@linux-mk1n:~/Java> java BinarySearchDemo
Please enter 5 values:
34
23
15
43
23
Sorting values...
15 23 23 34 43 
Please enter a key element to search:
34
Element 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.