C++ 二进制搜索 - 数组位置变量

Question

这应该只是一个愚蠢的小一般性问题（如果我能说清楚的话）。在查看我教授的示例和观看 YouTube 视频时，我注意到当人们设置二进制搜索时，他们声明但不定义数组位置的变量（例如，第一个、中间、最后一个或低、中、高）。

教授的例子片段：

int bsearch(const int list[], int first, int last, int searchItem){
  if(first <= last){
    int mid = (first + last) / 2;
    .......

How/Why 如果不为 first/last/mid 设置值，这项工作是否有效？

好的，这些回复很有道理。但是，在我教授的例子中，我很难理解这是在哪里发生的。我看到他 returns bsearch() 和我认为仍然是未定义参数的地方，后来又调用了 binarySearch()，但只有 3 个参数。我看到我被否决了；我不确定这个人为什么或在哪里希望我回答编程问题。无论如何，这是完整的代码：

#include <iostream>
using namespace std;

int bsearch(const int list[], int first, int last, int searchItem)
{
  if(first <= last) {
    int mid = (first + last) / 2;
    if(list[mid] == searchItem)
      return mid;
    else
      if(list[mid] > searchItem)
        return bsearch(list, first, mid-1, searchItem);
      else
        return bsearch(list, mid+1, last, searchItem);
  }
  else
    return -1;
}

// Non-recursive shell for the recursive binary search function.
// This function does not use "first" and "last" as its parameters.
int binarySearch(const int list[], int listLength, int searchItem)
{
  return bsearch(list, 0, listLength-1, searchItem);
}

int main() // testing recursive binarySearch function
{
  int a[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
  int item;
  cout << "Search item? ";
  cin >> item;
  cout << binarySearch(a, 10, item) << endl;
  return 0;
}

Answer 1

调用函数时将变量传递给函数。例如：

int main()
{
    int list[] = [1,2,3,4,5];
    cout << bsearch(list, 0, 4, 2);
    return 0;
}

Answer 2

我们用第三行的语句定义mid：

int mid = (first + last) / 2;

至于其他的，我们通过调用函数来定义first和last。例如：

a = bsearch(my_list, 1, 100, 55);

根据 int bsearch(const int list[], int first, int last, int searchItem) 这相当于说

int first = 1;
int last = 100;
int searchitem = 55;

我们这样做的部分原因是我们并不总是希望为每个二进制搜索定义相同的值，但更重要的是它允许我们调用二进制搜索 recursively。

那么你教授的例子呢？

让我们跟随函数调用，看看会发生什么！

在main()中我们有这行代码：

cout << binarySearch(a, 10, item) << endl;

我们看binarySearch，函数结构如下：

int binarySearch(const int list[], int listLength, int searchItem)

根据前面的例子，你也可以认为这是

const int list[] = a; //for now you can think of it as "= (the contents of a)", though it works a little different in reality
int listLength = 10;
int searchItem = item;

但现在我们进行另一个函数调用：

return bsearch(list, 0, listLength-1, searchItem);

但是等等！基于上一个示例，并了解 bsearch (bsearch(const int list[], int first, int last, int searchItem)) 的结构，我们可以看到这些变量也已定义！

某种程度上，你可以这样想！

//== main() ==

   int a[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
   int item;
   cin >> item;


//== int const list[] v       v int searchItem ==
//==     binarysearch(a, 10, item)             ==
//==       int listLength ^                    ==

   const int list[] = a;
   int listLength = 10;
   int searchItem = item;

//== int const list[] v          v int last                     ==
//==         bsearch(list, 0, listLength -1, searchItem)        ==
//==             int first ^                   ^ int searchItem ==

   const int list_bsearch = list;
   int first = 0;
   int last = listLength -1;
   int searchItem_bsearch = searchItem;

SO，我们定义的方式searchItem，比如你按照定义就行了

searchItem (bsearch) = searchItem (binarySearch) = 项目

注意 binarySearch 和 bsearch 是具有不同参数的不同函数。 "why do this" 背后的原因与递归有关，完全值得另一个问题。

还是卡住了？

这是一个非常简单的例子：

int fooAdd(int a, int b){

   //a and b are ints
   //by calling fooAdd(2, five) we set a = 2, and b = five (which was an int that happened to have the bvalue 5;

   return a +b;
}

int main(){
   int five = 5;   
   cout << fooAdd(2, five);
   return 0;
}

P.S。回应你的 "I see I've been downvoted; I'm not sure why or where this person expects me to turn with programming questions" 俏皮话。

stack overflow 的许多人都喜欢帮助您解决问题，但有时问题写得不是很清楚，或者有太多小问题无法真正帮助您解决问题。

不要认为通过投反对票，我们会阻止您提问。试着想象如何更好提出您的问题！

Answer 3

我猜提供的函数是递归的。因此，在您进入递归（函数调用自身）之前，您必须从其他地方调用该函数（例如：您从 main 调用 bsearch，然后它在 main 中 first 和 last 被设置为一些值）

int main ()
{
   bsearch(list, 0, 4, 2);
}

C++ 二进制搜索 - 数组位置变量

C++ Binary Search - Array Position Variables

c++

binary-search

那么你教授的例子呢？

还是卡住了？