How to write a simple and easy Binary search algorithm

How to write a simple and easy Binary search algorithm

Interview Questions  

Given a sorted array array[] of n elements and need to find the element 'val' present in the array or not by using Binary search technique.

NOTE: Binary search works only on sorted array.

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Example: 
Array[] = { 3, 7, 9, 10, 12, 15, 18, 23, 27, 29, 30, 32, 36, 39, 41, 43, 54 }
value = 10

OUTPUT: 3 (10 found in 3rd index)


Array[] = { 3, 7, 9, 10, 12, 15, 18, 23, 27, 29, 30, 32, 36, 39, 41, 43, 54 }
value = 99

OUTPUT: -1 (99 not present in the array)

Lets see simple java code for Binary Search.

public class BinarySearch {

 public static void main(String[] args) {

  int array[] = new int[] { 3, 7, 9, 10, 12, 15, 18, 23, 27, 29, 30, 32, 36, 39, 41, 43, 54 };
  int find = 10;

  int output = new BinarySearch().binarySearch(array, find);

  System.out.println(output);
 }

 public int binarySearch(int[] array, int val) {

  int p = 0, r = array.length - 1;

  while (p <= r) {
   int q = (p + r) / 2;
   if (array[q] == val)
    return q;
   if (array[q] > val)
    r = q - 1;
   else
    p = q + 1;
  }
  // number not present in the array
  return -1;
 }
}

OUTPUT:

3