自己写了个二分查找，但是函数里的打印信息和main里打印的值不一样，大家进来看一下!!

来智慧

1. #define _CRT_SECURE_NO_WARNINGS
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <string.h>
   
5. 
   
6. int search(int data[], int first, int last, int number)
   
7. {
   
8.     int mid = (last + first) / 2;
   
9. 
   
10.     if(data[mid] == number){
    
11.         printf("%d %d %d %d\n", mid, data[mid], first, last);
    
12.         return mid;
    
13.     }
    
14.     if(first >= last){
    
15.         return -1;
    
16.     }
    
17.     if(data[mid] > number){
    
18.         search(data, first, mid-1, number);
    
19.     }
    
20.     if(data[mid] < number){
    
21.         search(data, mid+1, last, number);
    
22.     }
    
23. }
    
24. 
    
25. int main()
    
26. {
    
27.     int data[] = {0, 1, 2, 2, 4, 4, 5, 8, 9, 9};
    
28.         int len = sizeof(data) / sizeof(data[0]);
    
29.         int x = search(data, 0, len-1, 5);
    
30.         printf("%d\n", x);
    
31.         system("pause");
    
32.         return 0;
    
33. }
    

复制代码

main中打印的值是8，然后在search函数中打印的Mid的值是6，用的是code::blocks编译器

来智慧

附上我的终端打印结果：
6 5 6 6
8
请按任意键继续. . .

qq1256740918

因为你这个二分查找，只找了一次。

qq1256740918

虽然有递归地查找，但是递归结果没有返回给自己，所以白白递归了。

qq1256740918

下面附上二分搜索迭代版的代码

1. int binary_search(int* array, int l, int r, int target)
   
2. {
   
3.     /*
   
4.         在数组下标为 [l, r] 的区间内搜索 target
   
5.     */
   
6. 
   
7.     static int mid;
   
8.     while(l <= r)
   
9.     {
   
10.         mid = (l + r) >> 1;
    
11. 
    
12.         if(array[mid] == target)
    
13.             return mid;
    
14.         else if(array[mid] < target)
    
15.             l = mid + 1;
    
16.         else
    
17.             r = mid - 1;
    
18.     }
    
19. 
    
20.     return -1;
    
21. }

复制代码

请注意搜索区间开闭的区别

来智慧

qq1256740918 发表于 2020-8-25 14:52
虽然有递归地查找，但是递归结果没有返回给自己，所以白白递归了。

啥意思？不是用了一个变量保存函数的返回值了吗？

qq1256740918

来智慧 发表于 2020-8-30 19:04
啥意思？不是用了一个变量保存函数的返回值了吗？

在大于（小于）的分支里，没有返回

baige

递归到return mid;之后就会回溯

baige

打错了