二分法查找 在对生成数进行排序时,出现数据的漏掉 最小的数无法排进去
```c++
#include <iostream>
#include <stdlib.h>
#include <time.h>
//二分查找(折半查找)
typedef int ElemType;
typedef struct {
ElemType* elem;
int TableLen;
}SSTable;
void ST_Init(SSTable &ST,int len){
ST.TableLen=len+1;//多申请一个位置,为了存哨兵,不使用哨兵也可以,为了和王道书上保持一致
ST.elem= (ElemType*)malloc(sizeof (ElemType)*ST.TableLen);
int i;
srand(time(NULL));//随机数生成
for(i=1;i<ST.TableLen;i++){
ST.elem[i]=rand()%100;//为了生成的随机数都在0到99之间
}
}
void ST_print(SSTable ST){
int i;
for(i=1;i<ST.TableLen;i++){
printf("%3d",ST.elem[i]);
}
printf("\n");
}
int Search_Seq(SSTable ST,ElemType key){
ST.elem[0]=key;//key作为0号元素 用于存放哨兵
int i;
for(i=ST.TableLen-1;ST.elem[i]!=key;i--);//从后往前找,找到了,i就是当前位置
return i;
printf("\n");
}
//二分查找
int BinarySearch(SSTable L,ElemType key){
int low=0;
int high=L.TableLen-1;
while(low<=high){
int mid=(low+high)/2;
if (key>L.elem[mid])//如果目标值大于中位数
{
low=mid+1;
} else if (key<L.elem[mid]){
high=mid-1;
} else{
return mid;
}
}
return -1;
}
//left指针和right指针指向的数组中的任意两个元素
int compare(const void *left,const void *right){
return *(int*)left-*(int*)right;//从小到大排序
//*(int*)right-*(int*)left 从大到小排序
}
int main() {
SSTable ST;
ST_Init(ST,10);//初始化随机10个数
ST_print(ST);
qsort(ST.elem,ST.TableLen,sizeof (ElemType),compare);
ST_print(ST);
ElemType key;
printf("please input search key:\n");
scanf("%d",&key);
int pos= BinarySearch(ST,key);
if (pos!=1){
printf("find key %d\n",pos);
} else{
printf("not find\n");
}
// int pos= Search_Seq(ST,key);
// if (pos)
// {
// printf("查找成功 位置为%d\n",pos);
// } else{
// printf("查找失败\n");
// }
return 0;
}