C语言二分法查找算法代码

算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。 基本思想：假设数据是按升序排序的，对于给定值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;

}

}