当前位置 博文首页 > ice_elephant的博客:数据结构算法之二分查找
二分查找法实质上是不断地将有序数据集进行对半分割,并检查每个分区的中间元素。再重
复根据中间数确定目标范围并递归实行对半分割,直到中间数等于待查找的值或是目标数不在搜
索范围之内!
#include<stdio.h>
#include<Windows.h>
int int_compare(const void *key1,const void *key2){
const int *ch1 = (const int*)key1;
const int *ch2 = (const int*)key2;
return (*ch1-*ch2);
}
int char_compare(const void *key1,const void *key2){
const char *ch1 = (const char*)key1;
const char *ch2 = (const char*)key2;
return (*ch1-*ch2);
}
// int(compare)(const void*key1,const void*key2)比较函数传入
int searchBinary(void *sorted,int len,int Elemsize,void *search,int(compare)(const void*key1,const void*key2)){
int left = 0;
int right = len-1;
int middle = 0;
int ret = 0;
while(left<=right){
middle = (right+left)/2;
//middle = (right-left)/2;
//int middle = (right-left)/2 right+1就是右边移 right-1就是左移是
ret = compare((char*)sorted+(Elemsize*middle),search);
if(ret==0){
return middle;//找到索引下标
}
if(ret>0){
//middle大于要找的数
right=middle-1;
//right--;
}
if(ret<0){
//middle小于要找的数
left = middle+1;
//right++;//这个不是二分查找了
}
}
//否则
return -1;//没有找到
}
int main(void){
int arr[]={1,3,7,9,11};
int search[]={0,-2,7,11,0,25};
int len = sizeof(arr)/sizeof(arr[0]);
for(int i=0;i<len;i++){
int index = searchBinary(arr,len,sizeof(int),&search[i],int_compare);
printf("serching %d,index: %d\n",search[i],index);
}
printf("字符查找!\n");
char ch[]={'a','b','d','e','f','s'};//按照顺序来
char chsearch[]={'S','s','f','d','e','w','a','s','0'};
for(int i=0;i<sizeof(chsearch)/sizeof(chsearch[0]);i++){
int index = searchBinary(ch,sizeof(ch)/sizeof(ch[0]),sizeof(char),&chsearch[i],char_compare);
printf("serching %c,index: %d\n",chsearch[i],index);
}
system("pause");
return 0;
}
cs