C语言二分法查找算法代码
时间:2025-07-11
时间:2025-07-11
算法:当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的。 基本思想:假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,
如果当前位置值等于x,则查找成功;若x小于当前位置值,则在数列的前半段中查找; 若x大于当前位置值则在数列的后半段中继续查找,直到找到为止。
验证代码
#include <iostream>
using namespace std;
#define ARRAY_SIZE 20
int main()
{
int array[ARRAY_SIZE];
int cnt;
for(cnt=0;cnt<ARRAY_SIZE;cnt++)
{
array[cnt]=cnt+1;
}
for(cnt=0;cnt<ARRAY_SIZE+3;cnt++)
{
cout<<DichotomySearch(cnt,array,ARRAY_SIZE);
}
return 0;
}
int DichotomySearch(int dat,int array[],int N)
{
int low,high;
low=0;high=N;//high=N 而不是N-1,这里主要是搜索最右边的值时low最大值是low=(low+high)/2迭代而来,low的初值比high小,(low+high)/2永远不可能等于high,也就是temppos=(low+high)/2不可能到达最右边的位置,换成N完美解决 int temppos=0;
while(1)
{
temppos=(low+high)/2;
if(array[temppos]==dat)return temppos;
else if(array[temppos]>dat)high=temppos;
else low=temppos;
if(low==high)//一下是可能出现的情况,比如搜索的值并不在这个数组里面的情况
{
if(array[low]==dat)return low; else return -1;
}
if(low==ARRAY_SIZE-1)
{
if(array[low]==dat)return low; else return -3;
}
if(low>high)return -2;
}
}
上一篇:双臂电桥测金属丝电阻率