# 基础数据结构和算法八：Binary search

Binary search needs an ordered array so that it can use array indexing to dramatically reduce the number of compares required for each search, using the classic and venerable binary search algorithm. We maintain indices into the sorted key array that delimit the subar- ray that might contain the search key. To search, we compare the search key against the key in the middle of the subarray. If the search key is less than the key in the middle, we search in the left half of the subarray; if the search key is greater than the key in the middle, we search in the right half of the subarray; otherwise the key in the middle is equal to the search key.  This implementation is worthy of careful study. To study it, we start with the recursive version of binary search implementation. This recursive rank() preserves the following properties:

■ If key is in the table, rank() returns its index in the table, which is the same as the number of keys in the table that are smaller than key.

■ If key is not in the table, rank() also returns the number of keys in the table that are smaller than key.

```public class BinarySearch {

// precondition: array a[] is sorted
public static int rank(int key, int[] a) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
// Key is in a[lo..hi] or not present.
int mid = lo + (hi - lo) / 2;
if      (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}

public static void main(String[] args) {

Arrays.sort(whitelist);

// read key; print if not in whitelist
while (!StdIn.isEmpty()) {
if (rank(key, whitelist) == -1)
StdOut.println(key);
}
}
}
```

Binary search in an ordered array with N keys uses no more than lg N

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊

1. 概念： Binary-search tree（BST）是一颗二叉树，每个树上的节点都有<=1个父亲节点，ROOT节点

Binary Search Jon Bentley以前说过类似的话:“90%的程序猿无法正确实现二分查找算法 就冲着这句话
Binary Search Jon Bentley曾经说过类似的话:“90%的程序员无法正确实现二分查找算法 就冲着这句话