修改后的二进制搜索数组

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

您的退出条件应该是 low >= high。然后您会找到第一个值，它小于或大于目标值（或者当然是您实际搜索的值）。然后你不再需要这个 if 语句：if (current < 0 || current > 14) 但你必须 check/adjust 循环后的结果。

Answer 2

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

另外，找不到物品时，有以下三种可能：

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

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

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

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

此外，您可能希望在找到该项目时提前退出。

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

while (!itemFound && low <= high)

你会发现这更容易推理。

修改后的二进制搜索数组

Modified Binary Search Array

c

arrays

algorithm

search

binary-search