c++ - 实现二分查找

Question

这是我的二进制搜索：

int binarySearch(int arr[], int value, int min, int max){
  int pos = -1;

  while (max >= min && pos == -1) {
    int mid = (max+min)/2;

    if(arr[mid] ==  value){
      pos = mid;
    }else if(arr[mid] < value){
      min = mid +1;
    }else if(arr[mid] > value){
      max = mid -1;
    }

  }
  return pos;
}

我这样称呼它：

 //Arr contain values 0-63
int i = binarySearch(arr, 64, 0, 64);

这些是中间值

32 48 56 60 62 63 64

在最后一次检查中，当数组中的最后一个位置是 63 时，我尝试访问 pos 64 处的元素。

我的实施有什么问题？

Answer 1

您的数组包含 0-63 的值（如您所述），并且您为 min 和 max 提供以下值：min=0，max=64。并更改以下行，以便您的代码可以处理高 int 值，否则可能会出现内存溢出。

       int mid = min+(max-min)/2;

上面的公式简化为 (max+min)/2 本身，但保护整数溢出。

Answer 2

当 max==min 时，你的长度为 0，所以你不应该进入循环。将条件更改为(max > min && ...)如果您的高水位是“结束时”（并且您的高水位可能应该是“结束时”，这是一个非常有用的模式）

哦，让它max = mid代替max = mid-1，因为 max 代表“一个超出结尾”而不是最后一个元素。

作为一种通用的编码风格改进，在编写这种代码时，会在索引范围内的所有地方抛出断言。这不仅可以更早地发现问题，还可以帮助您推断哪些值在范围内，哪些不在范围内......

Answer 3

试试这个代码

while (max > min && pos == -1) {
    int mid = (max+min)/2;

    if(arr[mid] ==  value){
        pos = mid;
    }else if(arr[mid] < value){
        min = mid;
    }else if(arr[mid] > value){
        max = mid;
    }
}