The Binary Search Algorithm

The Binary Search algorithm is a bit more complex to code, but it is much more powerful and efficient than the linear search algorithm. Note that the binary search can be done only on a SORTED collection of data!
This is a pseudo code:

Procedure: Binary-Search(a,x)
Inputs:
a: a sorted array to search in
x: the value we are searching for in a
Outputs:
The index position where a[i] == x or -1 if not found
Let assume that array a has the following structure a[p...q...r] where
p is the first index, r is the last index, and q is the index in the midpoint of the array.
Process:
1) Set the first index p to value 0 and the last index to a.length - 1
2) While p is less or equal to r do
a) set q to (p + r) / 2 and floor it to a whole number
b) if a[q] = x, return the index position (q)
c) if a[q] > x, set r to q - 1 else set p to q + 1
3) Return -1 if not found

Code in Java:

public static int binarySearch(int[]a, int x) {
  int p = 0;
  int r = a.length - 1;
  while (p <= r) {
    int q = (p + r)/2;
    if (a[q] == x) {
      return q;
    }
    if (a[q] > x ) {
      r = q - 1;
    } else {
      p = q + 1;
    }
 }
  return -1;
}

Or a more elegant way to write it:

	
public static int binarySearchModified(int[]a, int x) {
  int p = 0;
  int r = a.length - 1;
  while (p <= r) {
    int q = (p + r)/2;
    if (x < a[q]) r = q - 1;
    else if (x > a[q]) p = q + 1; 
    else return q;
  }
  return -1;
}