# 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;
}
```