[已解决]二叉查找算法

公子缠乡

int BinarySearchNonRecursive (int a[],int n,int data)
{
        int low=0;
        int high = n-1;
        while(low <= high)
        {
                int mid = low+(high-low)/2;
                printf("mid =%d ",mid);
                if (a[mid]==data)
                return mid;
                else if (data > a[mid])
                        low = mid+1;
                else
                        high = mid-1;
        }
        return -1;
}
// 为什么这个算法只能查找出1位数，查找不出2位数以上的数据

int main ()
{
        int a[20] = {0,1,2,3,4,124,6,7,8,9,10,123,678};
        printf("%d\n",BinarySearchNonRecursive (a,20,6));
        return 0;
}

最佳答案

月排行榜 / 总排行榜

柿子饼同学

2022-8-5 18:31:01

二分查找是需要一个有序的序列
所以你的序列要先排序, 另外你只有 13 个元素 , n 就不要填 20 了吧
另外 , low <= high 可能会导致死循环 , 可改成 low < high , high 改变的时候不用 -1
我这个是c++的 , 凑合看看吧
c 的排序函数可以用 qsort , 在 stdlib.h 里

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int bin_search(int a[], int n, int data){
   
5.     int l = 0, r = n; // 查找 [l, r)
   
6.     int mid;
   
7.     while(l < r){
   
8.         mid = (l + r) / 2;
   
9.         cout << "mid = " << mid << endl;
   
10.         if(a[mid] == data) return mid;
    
11.         else if(data > a[mid]) l = mid+1;
    
12.         else r = mid;
    
13.     }
    
14.     return -1;
    
15. }
    
16. 
    
17. int main(){
    
18.     ios::sync_with_stdio(0);
    
19.     cin.tie(0); cout.tie(0);
    
20.    
    
21.     int a[20] = {0, 1, 2, 3, 4, 124, 6, 7, 8, 9, 10, 123, 678};
    
22.    
    
23.     sort(a, a+13);
    
24. 
    
25.     cout << bin_search(a, 13, 678) << endl;
    
26. 
    
27.     return 0;
    
28. }
    

复制代码

跳转到最佳答案楼层

柿子饼同学

二分查找是需要一个有序的序列
所以你的序列要先排序, 另外你只有 13 个元素 , n 就不要填 20 了吧
另外 , low <= high 可能会导致死循环 , 可改成 low < high , high 改变的时候不用 -1
我这个是c++的 , 凑合看看吧
c 的排序函数可以用 qsort , 在 stdlib.h 里

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int bin_search(int a[], int n, int data){
   
5.     int l = 0, r = n; // 查找 [l, r)
   
6.     int mid;
   
7.     while(l < r){
   
8.         mid = (l + r) / 2;
   
9.         cout << "mid = " << mid << endl;
   
10.         if(a[mid] == data) return mid;
    
11.         else if(data > a[mid]) l = mid+1;
    
12.         else r = mid;
    
13.     }
    
14.     return -1;
    
15. }
    
16. 
    
17. int main(){
    
18.     ios::sync_with_stdio(0);
    
19.     cin.tie(0); cout.tie(0);
    
20.    
    
21.     int a[20] = {0, 1, 2, 3, 4, 124, 6, 7, 8, 9, 10, 123, 678};
    
22.    
    
23.     sort(a, a+13);
    
24. 
    
25.     cout << bin_search(a, 13, 678) << endl;
    
26. 
    
27.     return 0;
    
28. }
    

复制代码

dolly_yos2

柿子饼同学 发表于 2022-8-5 18:31
二分查找是需要一个有序的序列
所以你的序列要先排序, 另外你只有 13 个元素 , n 就不要填 20 了吧
另外  ...

这个代码似乎有点问题，试试在其它不变的前提下改成搜索 678 ？
问题出在对 low 和 high 的定义不明确。要注意到如果选择以 low < high 作为继续查找的条件，那么总有 mid < high 成立，换言之 high 对应的位置总不会被查找，其位于当前查找范围之外。因此应当设定当前查找范围为 [low, high) ，而在明确了这一点之后初始参数怎么传（初始范围怎么写）、搜索范围改变时谁加或减一谁不变也就不难想到了。

柿子饼同学

dolly_yos2 发表于 2022-8-5 18:55
这个代码似乎有点问题，试试在其它不变的前提下改成搜索 678 ？
问题出在对 low 和 high 的定义不明确。 ...

谢谢
刚刚把二楼的代码改了一下 , 现在没问题了
没弄清楚搜索的范围

公子缠乡

柿子饼同学 发表于 2022-8-5 18:31
二分查找是需要一个有序的序列
所以你的序列要先排序, 另外你只有 13 个元素 , n 就不要填 20 了吧
另外  ...

找出来了，是数组容量的问题，把n改成13就能查找出来了。