c - 3.3 书 k&r 中的上下文问题

Question

书中赋予我的功能----

/* binsearch find x in v[0] <= v[1] <= ... <= v[n-1] */
int bin( int x, int v[] , int n)
{
     int low, high , mid;

     low = 0;
     high = n -1;
     while( low <= high) {
            printf("LOL\n");
            mid = (low+high)/2;
            if( x < v[mid])
            high = mid + 1;
            else if ( x> v[mid])
            low = mid + 1;
            else return mid;

            }   
return -1;    
} 

这是函数的文本:二分查找首先将输入值 x 与数组 v 的中间元素进行比较。如果 x 小于大于中间值，则集中搜索表格的下半部分，否则搜索上半部分一半。无论哪种情况，下一步都是将 x 与所选一半的中间元素进行比较。将范围一分为二的过程一直持续到找到值或范围为空的。

为什么当我输入 int v[4] nexts elements = { 2,3,4,5} 和 for x = 2 时循环就会发生永远吗？

这是他们的错误吗？

Answer 1

您的代码有一个拼写错误。而不是

        if( x < v[mid])
        high = mid + 1;

应该有

        if( x < v[mid])
        high = mid - 1;

如果该函数被声明为会更好

int bin( int x, const int v[] , int n);

因为该算法不会改变数组本身，可以应用于常量数组。

考虑到有标准 C 函数 bsearch在 header <stdlib.h> 中声明