算法：改进的二进制搜索

本文介绍了算法：改进的二进制搜索的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我试图解决它基本上执行一个列表，其中先增加后减少的二进制搜索一个经典面试问题。虽然很明显，我们可以实现 O（log n）的我​​无法弄清楚什么是错的code以下，我已经写了：

I am trying to tackle a classical interview problem which is basically performing a binary search on a list which first increases then decreases. Even though it's obvious that we can achieve O(log n) I couldn't figure out what is wrong the code below that I've written:

#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有什么不对与code。 2），可以改进？

The reason why I ask this question is because I wonder two things. 1) What is wrong with the code since it fails for some values such as "14". 2) Can it be improved?

推荐答案

我觉得你的code没有处理好数组的增加和减少的部分。

I think your code does not handle well the increasing and decreasing part of the array.

不是告诉你究竟是如何做到这一点，这里有一些技巧，我希望你能完成它：）

Instead of telling you exactly how to do this, here is some tip and I hope you are able to finish it :)

一种解决方案是先找到其中数组去从提高以在O（LOGN）降序排列的点，则此基础上，在O（LOGN）执行二进制搜索的一个特殊版本。

One solution is to first find the point where the array goes from increasing order to decreasing order in O(logn), then based on that, perform a special version of binary search in O(logn).

让我知道，如果你不知道如何应对，我会介绍一些关于我的答案。

Let me know in case you don't know how to to this, I will explain more on my answer.