C# · 12月 20, 2021

二分查找(数据结构)

根据输入的N,随机生成N个数,然后输入查找元素,在数组中进行二分查找,找到返回位置,未找到返回0,(主要表达二分查找思路,所以省略了对数组元素的排序,直接调用了库函数sort())。

代码如下:

#include

#include

#include

using namespace std;

int a[1000];

//二分查找

int Search_Bin ( int a[],int key,int n ) {

int low,high,mid;

low = 1; high = n;

while (low <= high) {

mid = (low + high) / 2;

cout << "a["<< mid <<"]=" << a[mid] << endl;

if (key == a[mid]) return mid;

else if (key < a[mid]) high = mid – 1;

else low = mid + 1;

}

return 0;

}

//输出数组的数据

void show(int n)

{

for(int i = 1;i<=n;++i){

cout << a[i] << " ";

if(i % 5 == 0)

cout << endl;

}

cout << endl;

}

int main()

{

int n; //生成个数

int search;//带查找的数据

cout << "请输入序列的个数:n";

cin >> n;

for(int i = 1;i<=n;++i)

a[i] = rand()%200+1;

cout << "随机生成的序列是:n";

//先排序才能二分查找

sort(a,a+n);

show(n);

cout << "请输入要查找的数字:n";

cin >> search;

int result = 0;//查找结果 默认未找到为 0

result = Search_Bin(a,search,n);

if(result == 0) cout << "查找数据不存在!n";

else cout << "查找数据位于第" << result << "个位置n";

return 0;

}

注:排序函数sort()要用到头文件 

运行结果: