C语言折半查找法详细代码（假如有10个已排好序的数）

2024-11-01 17:33:34

推荐回答（4个）

回答（1）：

　　折半查找即二分查找，思想是：在一组有序的数据中查找一个数据，首先将要查找的数据与这组数中间的值比较，如果要查找的数据比它小，则在左半部分中继续查找；若比中间值大，则在右半部分中继续查找，相等的话就表示已找到，直接返回。

　　这样，每次查找都可以将查找范围缩小一半，以此达到O(log N)的时间复杂度。

　　折半查找代码如下：

int bsearchWithoutRecursion(intarray[],int low,int high,int target)
{
    while(low <= high)
    {
        int mid = (low + high) / 2;
        
        if(array[mid] > target)
            high = mid - 1;
        else if (array[mid] < target)
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}

回答（2）：

#include

int seek(int * pArr,int low,int high,int num);

void main()
{
int Arr[]={1,2,3,4,5,6,7,8,9,10};
int find,num;
printf("input a num to be found.\n");
scanf("%d",&num);
find = seek(Arr,0,9,num);
if (find == -1) printf("num=%d not found!\n",num);
else printf("num has been found!\nArr[%d] = %d\n",find,Arr[find]);

}

int seek (int *pArr,int low,int high,int num)
{//pArr 为数组名，该数组必须是排好序了（这是二分法的要求），这里按从小到大排序
int mid;
mid = (low+high)/2;
if ((low>=high)&&(pArr[mid]!=num))
return -1;
else
{
if (pArr[mid]==num)
return mid;
else if (pArr[mid]>num)
high = mid+1;//中间数字比要查的数还大，说明可能在中间段以前
else
low = mid-1;//同上，可能在中间段以后
return seek(pArr,low,high,num); //递归
}
}

回答（3）：

刚好，这是我前两天写的。
main(){
int a[15]={15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
int k,top,bot,mid;
scanf("%d",&k);
top=14;bot=0;
while(bot<=top){ /*注意这里的等于*/
mid=(top+bot)/2;
printf("bot=%d,top=%d,mid=%d,a[%d]=%d\n",bot,top,mid,mid,a[mid]);
if(k==a[mid]){
printf("%d",mid);
break;
}
else if(k>a[mid]) top=mid-1;
else bot=mid+1;
}
if(bot>top) printf("no");
getch();
}

回答（4）：

刚好，这是我前两天写的。
main(){
int
a[15]={15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
int
k,top,bot,mid;
scanf("%d",&k);
top=14;bot=0;
while(bot<=top){
/*注意这里的等于*/
mid=(top+bot)/2;
printf("bot=%d,top=%d,mid=%d,a[%d]=%d\n",bot,top,mid,mid,a[mid]);
if(k==a[mid]){
printf("%d",mid);
break;
}
else
if(k>a[mid])
top=mid-1;
else
bot=mid+1;
}
if(bot>top)
printf("no");
getch();
}