c - 改进的二分查找数组

Question

编辑:包括改进的代码。

我现在的逻辑是不正确的。我想要进行二分搜索来找到整数“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;

Answer 1

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

此外，当找不到该项目时，存在三种可能性:

1. wantToFind小于列表中最小的项目。
2. wantToFind大于列表中最大的项目。
3. wantTofind将位于列表中的某个位置。

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

在上面的情况 1 中，current将等于 0。

重点是不需要外循环。当二分查找失败时，current的值告诉您插入点。

此外，您可能希望在找到该元素后尽早离开。

最后，帮自己一个忙，把它变成 do...while进入while环形。即:

while (!itemFound && low <= high)

你会发现这更容易推理。