previous | start | next

## Binary Search

- Suppose we want to search the following data for 123.

  `v[0]` | `v[1]` | `v[2]` | `v[3]` | `v[4]` | `v[5]` | `v[6]` | `v[7]`
  `14` | `43` | `76` | `100` | `115` | `290` | `400` | `511`

- The last point in the first half of the data set, `v[3]`, is 100. That means we should look in the second half for a match.

  `v[4]` | `v[5]` | `v[6]` | `v[7]`
  `115` | `290` | `400` | `511`

- The last value in the first half of this sequence is 290; hence, the value must be located in the sequence

  `v[4]` | `v[5]`
  `115` | `290`

- The last value of the first half of this very short sequence is 115, which is smaller than the value we are searching for, so we must look in the second half.

  `v[5]`
  `290`

- Since there is only one element, the search easily shows that there is no match.

previous | start | next