c - 需要帮助在 C 中实现二进制搜索

Question

我正在尝试在 C 程序中编写迭代搜索。

伪代码看起来像这样:

while length of list > 0

look at middle of list

if number found, return true

else if number is too high, only consider

left half of list

else if number is too low, only consider

right half of list

return false

我已经实现了冒泡排序(我认为它有效)。这是我现在的代码。搜索目前是线性的。我需要以某种方式将其更改为二进制搜索(我更愿意迭代而不是递归地进行)。不过，我完全不知道该如何去做。有人可以帮我吗？:

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

#include "helpers.h"

/*
 * Returns true if value is in array of n values, else false.
 */

bool 
search(int value, int array[], int n)
{

// TODO: re-implement as binary search
int min = 0;
int max = n;
int i;

i=(min+max)/2;
    if(array[i] == value)
        {
        return true;
        }
    else if(min>=max)
        {
        return 1;
        }
    else if(array[i] > value)
        {
        max = i-1;
        }    
    else if(array[i] < value)
        {
        min = i+1;
        }
    return false;
}



/*
 * Sorts array of n values.
 */

void 
sort(int values[], int n)
{
//set smade to false to start
//declares the_end as n-1
bool smade = false;
int the_end = n-1;

// TODO: implement an O(n^2) sort
while(the_end > 0)
{
    for(int i = 0; i < the_end; i++)
    {
        int temp;
        if (values[i] > values[i+1])
        {
            temp = values[i];
            values[i] = values[i+1];
            values[i+1] = temp;
            smade=true;
        }
    

}
if(! smade)
    {
    break;
    }
the_end--;
}
return;
}

Answer 1

您只需将伪代码翻译成代码。我会给你一些更精炼的伪代码:

1) 将我们正在寻找的事物的最小可能位置 (min) 设置为零。

2) 将我们正在寻找的事物的最大可能位置 (max) 设置为最高可能位置。

3) 计算一个位置 loc 作为 (min+max)/2。

4) 检查loc 是否包含我们要查找的对象。如果是这样，停止，我们找到了。

5) 检查是否min>=max。如果是这样，停下来，它不在这里。

5) 如果loc处的物体太高，将max设置为loc-1。 (因为它可能的最大位置比 loc 小一个，因为 loc 太高了。)

6) 如果loc处的物体太低，将min设置为loc+1。 (同样的逻辑，反之亦然。)

7) 转到第 3 步。