二叉查找算法
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==data)
return mid;
else if (data > a)
low = mid+1;
else
high = mid-1;
}
return -1;
}
// 为什么这个算法只能查找出1位数，查找不出2位数以上的数据
int main ()
{
int a = {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 19:08 编辑
二分查找是需要一个有序的序列
所以你的序列要先排序, 另外你只有 13 个元素 , n 就不要填 20 了吧
另外 , low <= high 可能会导致死循环 , 可改成 low < high , high 改变的时候不用 -1
我这个是c++的 , 凑合看看吧{:10_278:}
c 的排序函数可以用 qsort , 在 stdlib.h 里
#include <bits/stdc++.h>
using namespace std;
int bin_search(int a[], int n, int data){
int l = 0, r = n; // 查找 [l, r)
int mid;
while(l < r){
mid = (l + r) / 2;
cout << "mid = " << mid << endl;
if(a == data) return mid;
else if(data > a) l = mid+1;
else r = mid;
}
return -1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int a = {0, 1, 2, 3, 4, 124, 6, 7, 8, 9, 10, 123, 678};
sort(a, a+13);
cout << bin_search(a, 13, 678) << endl;
return 0;
}
柿子饼同学 发表于 2022-8-5 18:31
二分查找是需要一个有序的序列
所以你的序列要先排序, 另外你只有 13 个元素 , n 就不要填 20 了吧
另外...
这个代码似乎有点问题，试试在其它不变的前提下改成搜索 678 ？
问题出在对 low 和 high 的定义不明确。要注意到如果选择以 low < high 作为继续查找的条件，那么总有 mid < high 成立，换言之 high 对应的位置总不会被查找，其位于当前查找范围之外。因此应当设定当前查找范围为 [low, high) ，而在明确了这一点之后初始参数怎么传（初始范围怎么写）、搜索范围改变时谁加或减一谁不变也就不难想到了。 本帖最后由 柿子饼同学 于 2022-8-5 19:14 编辑
dolly_yos2 发表于 2022-8-5 18:55
这个代码似乎有点问题，试试在其它不变的前提下改成搜索 678 ？
问题出在对 low 和 high 的定义不明确。 ...
谢谢
刚刚把二楼的代码改了一下 , 现在没问题了
没弄清楚搜索的范围 柿子饼同学 发表于 2022-8-5 18:31
二分查找是需要一个有序的序列
所以你的序列要先排序, 另外你只有 13 个元素 , n 就不要填 20 了吧
另外...
找出来了，是数组容量的问题，把n改成13就能查找出来了。
页:
[1]