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

Question

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

一段教授的例子:

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

如果不为 first/last/mid 设置值，这是如何/为什么工作的？

---

好吧，这些回应是有道理的。但是，在我教授的例子中，我很难理解这是在哪里发生的。我看到他在哪里返回 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

我们用第三行的语句定义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 是具有不同参数的不同函数。 “为什么这样做”背后的原因与递归有关，完全值得另一个问题。

还是卡住了？

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

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;
}

---

附言回应你的“我知道我被否决了；我不确定这个人为什么或在哪里希望我回答编程问题”的俏皮话。

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

不要认为通过否决投票，我们会阻止您提问。试着想象如何更好来问您的问题!