C++二分转顺序组合搜索函数陷入死循环问题求助

问题背景 #

刚接触C++，编写程序对比纯二分搜索与「当搜索区间大小小于18时切换为顺序搜索」的组合搜索的比较次数。数组为1000个1-1000的随机生成值，搜索前已排序。纯二分搜索运行正常，最大比较次数为10，但组合搜索进入顺序搜索循环后会无限执行，即使newListSize为6也无法跳出。

原组合搜索函数代码 #

template <class T>
void BinaryandSequentialSearch(const T arr[], int n, const T& search_key)
{
  int arrBegin = 0;
  int arrEnd = n - 1;
  int count = 0;
  int middle, i, newListSize;
  bool found = false;

  while (!found && arrBegin <= arrEnd)
  {
    count++;
    middle = (arrBegin + arrEnd) / 2;

    if (arr[middle] == search_key)
      found = true;
    else if (arr[middle] < search_key)
      arrBegin = middle + 1;
    else if (arrEnd - arrBegin < 18)
      {
        cout << "\nEntered sequenctial search.\n";
        newListSize = arrEnd - arrBegin;
        cout << newListSize << endl;

        for (i = 0; i < newListSize; i++)
        {
          count++;
          if (arr[middle] == search_key)
          {
            found = true;
            break;
          }
          middle++;
        }
      }
    else
      arrEnd = middle - 1;
  } 

  if (!found)
    cout << "\nThe value " << search_key << " is not in the array\n";
  else
  {
    cout << "\nThe value is located at index " << middle << " in the array"
         << endl << "Number of comparisons = " << count << endl;
  }
}

原main函数代码 #

int main()
{
  const int size = 1000;
  int A[size];
  int search_key;
  srand (time(NULL));

  for (int i = 0; i < size; i++)
    A[i] = rand() % 1000 + 1;

  Print(A, size, "Random unsorted array:");
  BubbleSort<int>(A, size);
  Print(A, size, "Array Sorted:");

  cout << "Enter an integer you want to search from array: ";
  cin >> search_key;

  //BinarySearch(A, size, search_key);
  BinaryandSequentialSearch(A, size, search_key);

  return 0;
}

错误原因 #

• 分支逻辑混乱：原代码在arr[middle] > search_key的情况下，先判断区间大小是否小于18，跳过了本该执行的arrEnd = middle -1操作，导致二分搜索的区间调整逻辑失效。
• 顺序搜索范围完全错误：
  • 计算newListSize时少加了1，正确的区间元素数应为arrEnd - arrBegin +1，但更致命的是，顺序搜索从middle开始往后遍历，而不是遍历当前的整个搜索区间[arrBegin, arrEnd]。
  • 循环中一直判断arr[middle] == search_key，如果目标不在middle到数组末尾的位置，middle会不断递增甚至越界，导致无限循环。
• 顺序搜索后未终止外层循环：即使顺序搜索完成（找到或没找到），外层的while循环仍会继续执行，因为found状态未正确触发循环退出，或者区间边界未更新。

修复后的组合搜索函数 #

#include <iostream>
using namespace std;

template <class T>
void BinaryandSequentialSearch(const T arr[], int n, const T& search_key)
{
    int arrBegin = 0;
    int arrEnd = n - 1;
    int count = 0;
    int middle, i;
    bool found = false;

    while (!found && arrBegin <= arrEnd)
    {
        // 先判断是否切换顺序搜索：区间元素数小于18时触发
        if (arrEnd - arrBegin + 1 < 18)
        {
            cout << "\n进入顺序搜索.\n";
            // 遍历当前整个搜索区间
            for (i = arrBegin; i <= arrEnd; i++)
            {
                count++;
                if (arr[i] == search_key)
                {
                    found = true;
                    middle = i; // 记录找到的索引
                    break;
                }
            }
            // 顺序搜索结束后直接退出外层循环，避免重复执行
            break;
        }

        // 执行二分搜索步骤
        count++;
        // 用arrBegin + (arrEnd - arrBegin)/2避免整数溢出
        middle = arrBegin + (arrEnd - arrBegin) / 2;

        if (arr[middle] == search_key)
        {
            found = true;
        }
        else if (arr[middle] < search_key)
        {
            arrBegin = middle + 1;
        }
        else
        {
            arrEnd = middle - 1;
        }
    } 

    if (!found)
    {
        cout << "\n值 " << search_key << " 不在数组中\n";
    }
    else
    {
        cout << "\n值位于数组索引 " << middle << endl
             << "比较次数 = " << count << endl;
    }
}

修复要点 #

• 调整分支顺序：先判断是否需要切换顺序搜索，再执行二分搜索逻辑，避免分支覆盖导致的逻辑错误。
• 正确遍历区间：顺序搜索从arrBegin开始到arrEnd结束，覆盖当前所有待搜索元素。
• 终止外层循环：顺序搜索完成后直接break外层while，防止重复执行循环体。
• 优化索引计算：替换(arrBegin+arrEnd)/2为arrBegin + (arrEnd - arrBegin)/2，避免两个大整数相加导致的溢出问题。

内容的提问来源于stack exchange，提问作者freeridin