我如何使用此二进制搜索函数的修改后的 max/min 值创建新数组

Question

我正在尝试实现二进制搜索功能，我想知道如何使用新的 min/max 值修改新数组。另外我是 C++ 的新手所以谁能告诉我这是否是二进制搜索的正确实现？谢谢。

#include <iostream>

using namespace std;

bool doSearch(int arr, int target)
{
int min = 0;    
int max = arr.length() - 1;
while(min != max)
{
    int avg = (min + max)/2;        
    if(arr[avg] < taget){
        min = avg + 1
    }
    else if(arr[avg] > target){
        max = avg - 1;

    else if (arr[avg] == target)
        {
            return avg;
        }   
    }
}
return -1;

}

int main()
 {
int primes[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,61,67,71,73,79,83};
int result = doSearch( primes , 47 );
cout<<"Found prime at index " <<result;

}

Answer 1

您需要进行以下更改。

首先将 doSearch 的 return 类型从 bool 更改为 int。
然后在需要的地方加上;如min = avg + 1;
将您的 while 循环条件更改为 while(min <= max)
然后将 main() 中的代码更改为

if(result != -1) cout<<"Found prime at index "<<result; else cout<<" Not found";

Answer 2

#include <iostream>
using namespace std;


template<size_t N>
int doSearch(int(&arr)[N], int target)
{
    int max = N - 1;
    int min = 0;
    int returnValue = -1;


    while (min <= max)
    {
        int avg = (min + max) / 2;
        if (arr[avg] < target) {
            min = avg + 1;
        }
        else if (arr[avg] > target) {
            max = avg - 1;
        }
        else if (arr[avg] == target)
        {
            return  avg;
        }

    }
    return returnValue;
}


int main()
{
    int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };

    int result = doSearch(primes, 47);
    cout << "Found prime at index " << result<<endl;


    system("PAUSE");
    return 0;
}

您的代码中有一些错误 - 语法和逻辑错误。您的第一个错误是找到数组长度的过程。我使用了一种不太典型的方法来查找长度——还有其他方法可以这样做，但我使用模板来完成它，因为它更有趣。同样在你的 while 循环中，你有它 while(min!=max) 这永远不会得到答案，因为如果答案位于最小值和最大值相同的位置 - 例如你的数组，它就会停止。此外，您的原始函数返回一个布尔值 - 这没有任何意义，因为您正在寻找 int 的位置。这段代码中可能仍然存在一些错误。请随时指正。希望对您有所帮助！

Answer 3

bool doSearch

如果要return索引，那么应该是

int doSearch

doSearch(int arr, int target)

应该改为

doSearch(int arr[], int size, int target)

因为在c++中，没有预定义的函数来获取数组的长度。所以你的函数看起来像

int doSearch(int arr[], int size, int target)

while(min != max)

应该是

while (min <= max)

因为，否则，当目标位于 min = max 的索引处时，搜索将不会 return 索引。即，考虑的情况 int arr[] = {0}; 和函数调用 doSearch(arr, 1, 0);。

要查找数组的大小，您可以使用

sizeof(primes) / sizeof(primes[0])

所以你的函数调用变成了

int size = sizeof(primes) / sizeof(primes[0]);
int result = doSearch(primes, size, 47);

请注意，您不能像上面那样在 doSearch 函数中计算大小，因为数组是作为指向函数的指针传递的。

此外，一旦进入if (arr[avg] < target)和else if (arr[avg] > target)，就不需要检查剩余的条件，所以你可以使用continue进入while循环的下一次迭代，即

if (arr[avg] < target)
{
    min = avg + 1;
    continue;
}
else if (arr[avg] > target)
{
    max = avg - 1;
    continue;
}

最后，由于您的 main 需要一个 int 作为 return，您可以 return 0 并且在 returning 之前使用 system("pause")，以便控制台 window 没有一显示结果就关闭

system("pause");
return 0;

我如何使用此二进制搜索函数的修改后的 max/min 值创建新数组

How could I create new arrays with the modified max/min values for this Binary Search function

c++

binary-search