数组中的二进制搜索无法正常工作

Question

// function for binary search in array
#include <iostream>
using namespace std;
int binSrch(int arr[], int n, int key)
{
    int s = 0, e = n; // s for starting and e for ending
    int mid = (s + e) / 2;
    while (s <= e)
    {
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] > key)
            e = mid - 1;
        else
            s = mid + 1;
    }
    return -1;
}
int main()
{
    int n, key;
    cout << "enter no. of elements" << endl;
    cin >> n;
    int arr[n];
    cout << "enter array " << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    cout << "enter key" << endl;
    cin >> key;
    cout << binSrch(arr, n, key);
    return 0;
}

此数组二进制搜索代码不起作用。

对于某些数组，程序卡住了。我不知道哪里做错了。

我输入的是排序格式。

PS C:\Users\anmol\Desktop\c++projectwork> g++ .\binSearchArrFun.cpp
PS C:\Users\anmol\Desktop\c++projectwork> ./a
enter no. of elements
6
enter array 
2
3
4
5
6
7
enter key
8

它只是卡在这里而不是给出-1

Answer 1

假设您将 n 作为数组的大小传递，您应该给出 e = n-1，因为数组是基于 0 索引的，这就是您可能得到错误答案的地方。而且你还应该在每次迭代后计算 mid，所以它应该在 while loop.

内

此外，您应该mid = s +(e-s)/2以避免溢出。

Answer 2

我修改了你的代码。运行它应该清楚发生了什么。

#include <iostream>

using namespace std;

int binSrch(int arr[], int n, int key)
{
  int s = 0, e = n; // s for starting and e for ending
  int mid = (s + e) / 2;
  while (s <= e)
  {
    if (arr[mid] == key)
      return mid;
    else if (arr[mid] > key)
    {
      cout << "e = mid - 1;\n";
      e = mid - 1;
    }
    else
    {
      cout << "e = mid - 1;\n";
      s = mid + 1;
    }
  }
  return -1;
}

int main()
{
  int n = 4, key = 3;
  int arr[100] = { 1,3,4,10 };

  cout << binSrch(arr, n, key);
  return 0;
}

您可以使用此修改后的 main 进行测试。它会输出不起作用的测试用例。

int main()
{
  int n = 4;
  int arr[] = {1,3,4,10,11};

  // check for each element of arr if it is found
  // at the right position

  int index = 0;
  for (auto testval : arr)
  {
    if (! binSrch(arr, n, testval) == index)
      cout << "not OK for case" << testval << "\n";

    index++;
  }

  // check if 0 and 100 are not found

  if (binSrch(arr, n, 0) != -1)
    cout << "not OK for case" << 0 << "\n";

  if (binSrch(arr, n, 100) != -1)
    cout << "not OK for case" << 100 << "\n";  

  return 0;
}

数组中的二进制搜索无法正常工作

Binary search in array is not working properly

c++

binary-search

visual-studio