c - 修改后的二进制搜索数组

编辑：包括改进的代码。

我当前的逻辑不正确。我想进行一个二进制搜索，该搜索将找到整数“ wantToFind”，如果不在数组中，它将从wantToFind中减去1，直到找到它为止。

我从一个较大的程序中减去了这个值，该程序可以保证数组中的第一个项目将是最低的wantToFind（我们想要查找的值）。

但是，尽管遵循二进制搜索约定，但在寻找更高的数字（例如88）时，程序仍会卡住。

float list[15] = {60,62,64,65,67,69,71,72,74,76,77,79,81,83,84};

// binary search
int wantToFind = 88; //other tests are 65, 61, 55
bool itemFound = false;

int current = 0;
int low = 0;
int high = 14;

current = (low+high)/2;
//int previousCurrent = -1;

do {
    do {
        //if 61 < 72
        if (wantToFind < list[current])
        {
            //smaller
            //previousCurrent = current;
            high = current - 1;
            current = (low+high/2);
        }
        else if (wantToFind > list[current])
        {
            //bigger
            //previousCurrent = current;
            low = current + 1;
            current = (low+high/2);
        }
        else{
            if(wantToFind == list[current])
            {
                itemFound = true;
            }
        }

    } while (low >= high);

    if (itemFound == false)
    {
        wantToFind--;
    }
} while (itemFound == false);

printf("\n%d", wantToFind); //which will be a number within the list?
    return 0;

最佳答案

我无法想象你为什么要while (low >= high)。这将导致循环第一次终止。我很确定您想要while (low <= high)。

另外，当找不到该物品时，有三种可能性：


wantToFind小于列表中的最小项目。
wantToFind大于列表中最大的项目。
wantTofind将位于列表中的某处。


在情况2和3中，当退出内部循环时，current的值将比包含小于wantToFind的第一项的索引大一个。

在上述情况1中，current等于0。

关键是不需要外部循环。当二进制搜索失败时，current的值会告诉您插入点。

另外，您可能想在找到该物品时提早购买。

最后，帮自己一个忙，将do...while变成while循环。那是：

while (!itemFound && low <= high)

您会发现推理起来容易得多。