# Binary Search

Jump to navigation
Jump to search

**Binary Search** searches by exploiting the ordering in a sequence in splitting it in half each time.

A real-life example of **Binary Search** would be if you were to look for the name "Larry" in a phonebook, you would first go to the middle of the phonebook, if "Larry" is before the middle entry, you rip and throw away the latter half, and then do the same thing.

**Binary Search** is an example of divide and conquer
paradigm. It runs in time on an array of length .

## Pseudo-code[edit]

Note:Its always safe to choose the mid point by taking mid=left + (right-left)/2 because it prevents the overflow when the array index is large and both right and left fall near the highest index

Recursively:

/* Searches value 'x' in sorted array a[left], a[left+1], ..., a[right]. Returns the index of 'x' in array, or -1 if it cannot be found. */ search(a, left, right, x) if left > right then return -1 mid := left+floor((right-left) / 2) if a[mid] = x then return mid else if a[mid] > x then return search(a, left, mid-1, x) else return search(a, mid+1, right, x)

Iteratively (in C):

```
// Search value 'x' in array a [0], a [1], ..., a [n - 1]
int search (int a [], int n, int x) {
int r, c;
for (int l = 0, r = n - 1; l <= r;) {
c = l + (r - l) / 2;
if (a [c] > x) r = c - 1;
else if (a [c] < x) l = c + 1;
else return c;
}
return -1;
}
```