c++ - 这个简单的 c++ 程序永远运行，我不明白为什么

Question

它编译得很好，打印了第一个“开始”，但它就停在那里。任何帮助是极大的赞赏。我花了几个小时试图找出问题所在，并尝试在几个不同的 IDE 中运行它。我认为它在 while 循环中失败了。

#ifndef TERNARY_SEARCH_H
#define TERNARY_SEARCH_H

#include <cstdlib>
#include <iostream>


template <typename ArrayLike, typename T>
int ternary_search(const ArrayLike& array, const T& value, int low, int high) 
{
/* 
 * low is the lowest possible index, high is the highest possible index
 * value is the target value we are searrching for
 * array is the ascending order array we are searching 
 */


bool found = false; 

while(!found)
{
    int lowerThirdIndex =   (((high - low)/(3)) + low);
    int upperThirdIndex = (2*((high - low)/(3)) + low);

// search lower third
    if (array[lowerThirdIndex] == value) 
    {
      return lowerThirdIndex;
      found = true;
    }
    else if (array[lowerThirdIndex] > value)
    {
        high = lowerThirdIndex;
    }
    else // array[lowerThirdIndex] < value
    {
        low = lowerThirdIndex;
    }

    //search upper third
    if (array[upperThirdIndex] == value) 
    {
      return upperThirdIndex;
      found = true;
    }
    else if (array[upperThirdIndex] > value)
    {
        high = upperThirdIndex;
    }
    else // array[upperThirdIndex] < value
    {
        low = upperThirdIndex;
    }

}
  return -1;
}


#endif /* TERNARY_SEARCH_H */


//main.cpp
#include "ternary_search.h"
using namespace std;

int main() {
  cout << "start";
  int nums[] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
  for (int i = 0; i <= 90; i += 10) {
    if (ternary_search(nums, i, 0, 10) != i / 10) {
      std::cout
        << "Searching for " << i << " returned index "
        << ternary_search(nums, i, 0, 10) << " instead of "
        << i / 10 << "." << std::endl;
      return 1;
    }

    // search for something that doesn't exist.
    if (ternary_search(nums, i + 1, 0, 10) != -1) {
      std::cout
        << "Searching for " << i + 1 << " returned index "
        << ternary_search(nums, i + 1, 0, 10) << " instead of -1."
        << std::endl;
      return 1;
    }
  }
  std::cout << "On this small example, your search algorithm seems correct.\n";
  return 0;
}

Answer 1

您的 ternary_search 函数无法在搜索表中找不到值时返回。仅当它在表中找到与您传入的值完全匹配的元素时才返回。

由于函数的第二次调用是用 i+1 调用的——它是 1——它不是你的表的成员，所以你的三元搜索函数永远不会退出。