4

我正在尝试解决一个经典的面试问题，该问题基本上是在列表上执行二进制搜索，该列表首先增加然后减少。即使很明显我们可以实现O(log n)我无法弄清楚我编写的下面的代码有什么问题：

#include <iostream>

using namespace std;


int binarySearch(int *A, int low, int high, int key)
{
    while(low < high)
    {
        int mid = (low + high) / 2;
        if(key < A[mid])
        {
            if(A[mid - 1] < A[mid] && A[mid] < A[mid + 1])
                high = mid - 1;
            else
                low = mid + 1;
        }
        else if(key > A[mid])
        {
            if(A[mid - 1] < A[mid] && A[mid] < A[mid + 1])
                low = mid + 1;
            else
                high = mid - 1;
        }
        else
            return mid;
    }

    return -(low + 1);
}


int main()
{
    const int SIZE = 8;
    int A[SIZE] = {3,5,7,14,9,8,2,1};
    cout<<binarySearch(A, 0, SIZE, 14);
    return 0;
}

我之所以问这个问题，是因为我想知道两件事。1）代码有什么问题，因为它对于某些值（例如“14”）失败。2）可以改进吗？

4

3 回答 3

6

我认为您的代码不能很好地处理数组的增加和减少部分。

这里没有告诉你确切的方法，而是一些提示，我希望你能够完成它:)

一种解决方案是首先在 O(logn) 中找到数组从升序到降序的点，然后基于此，在 O(logn) 中执行特殊版本的二进制搜索。

如果您不知道该怎么做，请告诉我，我将详细解释我的答案。

于 2013-06-27T19:15:17.890 回答
2

这是一个更完整的解决方案（仅供参考）

一种解决方案是首先在 O(logn) 中找到数组从升序到降序的点，然后基于此，在 O(logn) 中执行特殊版本的二进制搜索。

第一部分可以通过array[i-1] <= array[i]使用专门的二进制搜索找到最后一个点来实现，其中mid索引移动条件是是否array[mid-1] <= array[mid]而不是是否array[mid] <= target。

示例代码

为了防止我成为面试黑客，下面只展示如何处理没有任何重复的数组。如有必要，该代码将很快删除：

#include <stdio.h>
#include <stdlib.h>

int find_change_point(int array[], int low, int high, int array_size) {
  int mid;
  for (mid = (low + high) / 2; low <= high; mid = (low + high) / 2) {
    // if true, it implies the point is on the higher side
    if (array[mid - 1] <= array[mid]) {
      if (mid == array_size - 1) {
        return mid;
      }
      // since we already handles equality, only > is needed.
      if (array[mid] > array[mid + 1]) {
        return mid;
      }
      low = mid + 1;
    } else {
      // then simply imply the point is on the lower part
      high = mid - 1;
    }
  }
  return mid;
}

int main() {
  const int SIZE_1 = 8;
  int array_1[SIZE_1] = {3,5,7,14,9,8,2,1};
  int change_point = find_change_point(array_1, 0, SIZE_1 - 1, SIZE_1);
  printf("change_point_1 = %d\n", change_point);

  const int SIZE_2 = 9;
  int array_2[SIZE_2] = {3,5,7,14,15,16,17,19, 20};
  change_point = find_change_point(array_2, 0, SIZE_2 - 1, SIZE_2);
  printf("change_point_2 = %d\n", change_point);

  const int SIZE_3 = 9;
  int array_3[SIZE_3] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
  change_point = find_change_point(array_3, 0, SIZE_3 - 1, SIZE_3);
  printf("change_point_3 = %d\n", change_point);
}

输出是：

change_point_1 = 3
change_point_2 = 8
change_point_3 = 0

处理重复，你需要找到它的重复序列的左端和右端，并验证它们是递增序列还是递减序列。

第二部分有很多品种。一种简单的解决方案是将它们视为两个数组，并对每个子数组执行一次二进制搜索以找到您的目标元素。

于 2013-06-27T19:31:50.383 回答
0

For your code i think to many branch like "if" operation . Following is simple pseudocode for your reference:

while(1 < (high - low)){
     int mid = (low + high) >> 1;
     (key < A[mid]) ? high = mid : lo = mid;
}
return (key == A[lo]) ? lo : -1;

Hope this can be help you.

于 2013-11-27T16:03:32.720 回答