二分查找算法实现

jack1007

二分查找算法很容易忽略了边界问题，导致在某些情况下查找失败，下面写了一个，斟酌了下边界问题，应该没有问题了，如果还有什么方法实现的，还请大家分享。

1. #include <stdio.h>
   
2. 
   
3. int search(int *arr, int keys, int value);
   
4. 
   
5. int
   
6. main()
   
7. {
   
8.   int arr[] = {1, 2, 3, 5, 7, 11, 18, 24, 53};
   
9.   int key;
   
10.   int value = arr[7];
    
11.   int keys = sizeof(arr) / sizeof(arr[0]);
    
12.   printf("There are %d keys\n", keys);
    
13.   key = search(arr, keys, value);
    
14.   printf("The key of value %d is %d\n", value, key);
    
15.   return 0;
    
16. }
    
17. 
    
18. int
    
19. search(int *arr, int keys, int value)
    
20. {
    
21.   int left = 0;
    
22.   int right = keys - 1;
    
23.   int midle;
    
24.   while (left <= right) {
    
25.     midle = (left + right) / 2;
    
26.     if (arr[midle] > value)
    
27.       right = midle -1;
    
28.     else if (arr[midle] < value)
    
29.       left = midle + 1;
    
30.     else
    
31.       return midle;
    
32.   }
    
33. 
    
34.   return -1;
    
35. }

复制代码

lxyscls_cu

int keys = sizeof(arr) / sizeof(arr[0]);

这个好像有问题吧，越界了，right应该是实际的数组右边界{:3_189:}

基本就这么样么，还有递归版本，《编程珠玑2》上面有个完整的讨论，特别是测试这个算法的部分，讲得满好的，可惜忘记了{:3_188:}

linux_c_py_php

二分是最基础的, lower_bound, upper_bound才是考察一个人会不会思考如何设计二分的关键.

jack1007

确实，search函数里面的right应该是keys - 1，已经改过来了
int right = keys - 1;