作者：liubird

来源：http://blog.chinaunix.net/uid-1844931-id-3337784.html

前几天在论坛上看到有统计说有80%的程序员不能够写对简单的二分法。二分法不是很简单的吗？ 这难道不是耸人听闻？

其实，二分法真的不那么简单，尤其是二分法的各个变种。 最最简单的二分法，就是从一个排好序的数组之查找一个key值。 如下面的程序：

这个程序，相信只要是一个合格的程序员应该都会写。 稍微注意一点， 每次移动left和right指针的时候，需要在mid的基础上+1或者-1， 防止出现死循环， 程序也就能够正确的运行。

但如果条件稍微变化一下， 你还会写吗？如，数组之中的数据可能可以重复，要求返回匹配的数据的最小（或最大）的下标；更近一步， 需要找出数组中第一个大于key的元素（也就是最小的大于key的元素的）下标，等等。 这些，虽然只有一点点的变化，实现的时候确实要更加的细心。 下面列出了这些二分检索变种的实现。

1 找出第一个与key相等的元素

2 找出最后一个与key相等的元素

3. 查找第一个等于或者大于Key的元素

1. int searchFirstEqualOrLarger(int *arr, int n, int key)

2. {

3. int left=0, right=n-1;

4. while(left<=right) {

5. int mid = (left+right)/2;

6. if(arr[mid] >= key) right = mid-1;

7. else if (arr[mid] < key) left = mid+1;

8. }

9. return left;

10. }

4. 查找第一个大于key的元素

1. int searchFirstLarger(int *arr, int n, int key)

2. {

3. int left=0, right=n-1;

4. while(left<=right) {

5. int mid = (left+right)/2;

6. if(arr[mid] > key) right = mid-1;

7. else if (arr[mid] <= key) left = mid+1;

8. }

9. return left;

10. }

5. 查找最后一个等于或者小于key的元素

1. int searchLastEqualOrSmaller(int *arr, int n, int key)

2. {

3. int left=0, right=n-1;

4. while(left<=right) {

5. int m = (left+right)/2;

6. if(arr[m] > key) right = m-1;

7. else if (arr[m] <= key) left = m+1;

8. }

9. return right;

10. }

6. 查找最后一个小于key的元素

1. int searchLastSmaller(int *arr, int n, int key)

2. {

3. int left=0, right=n-1;

4. while(left<=right) {

5. int mid = (left+right)/2;

6. if(arr[mid] >= key) right = mid-1;

7. else if (arr[mid] < key) left = mid+1;

8. }

9. return right;

10. }

下面是一个测试的例子：

1. int main(void)

2. {

3. int arr[17] = {1,

4. 2, 2, 5, 5, 5,

5. 5, 5, 5, 5, 5,

6. 5, 5, 6, 6, 7};

7. printf("First Equal : %2d \n", searchFirstEqual(arr, 16, 5));

8. printf("Last Equal : %2d \n", searchLastEqual(arr, 16, 5));

9. printf("First Equal or Larger : %2d \n", searchFirstEqualOrLarger(arr, 16, 5));

10. printf("First Larger : %2d \n", searchFirstLarger(arr, 16, 5));

11. printf("Last Equal or Smaller : %2d \n", searchLastEqualOrSmaller(arr, 16, 5));

12. printf("Last Smaller : %2d \n", searchLastSmaller(arr, 16, 5));

13. system("pause");

14. return 0;

15. }

最后输出结果是：

1. First Equal : 3

2. Last Equal : 12

3. First Equal or Larger : 3

4. First Larger : 13

5. Last Equal or Smaller : 12

6. Last Smaller : 2

很多的时候，应用二分检索的地方都不是直接的查找和key相等的元素，而是使用上面提到的二分检索的各个变种，熟练掌握了这些变种，当你再次使用二分检索的检索的时候就会感觉的更加的得心应手了。