Question

一道数据结构练习题

随机生成1000个实数，按照升序保存在顺序表中，利用二分法实现检索。

谢谢！采纳回答后继续追加分！

Answer 1

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#define THRESHOLD 1e-6
void quickSort(double a[],int l, int r)
{
	if(l>=r) return;
	
	int i=l;
	int j=r;
	double k=a[l];
	while(i<j)
	{
		while(i<j&&k<=a[j]) j--;
		a[i]=a[j];
		while(i<j&&k>=a[i]) i++;
		a[j]=a[i];
	}
	a[i]=k;
	
	quickSort(a, l, i-1);
	quickSort(a, i+1, r);
}
void sort(double a[], int n)
{
	quickSort(a, 0, n-1);
}
int binSearch(double a[], double x, int n)
{
	int l=0, h=n;
	while(l<=h)
	{
		int mid=(l+h)/2;
		double diff=a[mid]-x;
		if(fabs(diff)<=THRESHOLD) return mid;
		else if(diff>THRESHOLD) h=mid-1;
		else l=mid+1;
	}
	return -1;
}
int main()
{
	srand((unsigned)time(NULL));
	double a[1000];
	for(int i=0;i<1000;i++)
		a[i]=rand()/(RAND_MAX+1.0);
	printf("Generate 1000 random real numbers done.\n");
	sort(a, 1000);
	printf("Sort done, input a 6 decimal places number between 0 and 1 to search: ");
	double d;
	scanf("%lf",&d);
	int find=binSearch(a, d, 1000);
	if(find==-1)
	{
		printf("%f is not in array a.\n", d);
	}
	else
	{
		printf("Found a[%d]=%f\n", find, d);
	}
	return 0;
}

追问

感谢！
可否给一些关键步骤注释？
追加200分，谢谢！

追答

quickSort 快速排序
sort 排序包装函数
binSearch 二分搜索
rand()/(RAND_MAX+1.0); 生成随机数

Answer 2

#include<iostream>
#include<algorithm>
using namespace std;
int  number, a[1001];
void f(int low, int high)
{
	if (low > high)
	{
		cout<<"未检索到"<<endl;
		exit(0);
	}
	int mid = (low + high) / 2;
	if (number == a[mid])
	{
		cout<<"检索下标为:"<<mid<<endl;
		exit(0);
	}
	else if (number >a[mid])
	{
		low = mid + 1;
		f(low, high);
	}
	else
	{
		high = mid - 1;
		f(low, high);
	}
}
void main()
{
	int  i, low = 1, high = 1000;
    cin>>number;//待检索数
	for (i = 1; i <= 1000; i++)
	{
		a[i] = rand() % 1000;//生成随机实数
	}
	sort(a+1, a+1001);//排序
	f(low, high);//二分查找
}