在旋转数组中查找最小值

Question

我试图在已旋转的排序数组中找到最小元素。

示例：

     1 2 3 4 5 => sorted

     3 4 5 1 2 => Rotated => Find the min in this in O(log n)

我试过写代码:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int bs(vector<int> a)
{
    int l =0, r = a.size()-1;

    while(l<=r)
    {
        int mid = l + (r-l)/2; // Mid guaranteed to be in range

        if(a[mid-1]>a[mid]) return a[mid];

        if(a[mid]>a[l])
        {
            l=mid+1 ; continue;
        }
        else
        {
            r = mid-1 ; //Mid has been checked
        }
    }
}

int main()
{
  vector<int> a = {1,2,3,5,6,7,8,9,10};
  rotate(a.begin(),a.begin()+4,a.end()); //  Make 6 the head 
  for(auto x:a) cout<<x<<endl;
  cout <<"Min is " <<bs(a) <<endl;
  return 0;
}

我得到输出：

，这显然是错误的。我想我正在操纵二进制搜索条件以适应我的问题，但我无法弄清楚哪里出了问题。

我的方法和this类似，我觉得我做的逻辑是正确的，这当然是错误的想法。

Answer 1

<algorithm> 提供了一种用于查找最小元素的内置方法，称为 min_element（除了 max 和 minmax）。

你可以这样使用它：

std::vector<int>::iterator result = std::min_element(std::begin(a), std::end(a));
std::cout << "Min is " << std::distance(std::begin(a), result);

而且根本不必使用 bs() 方法。

Answer 2

使用

简单地找到旋转点

auto sorted_end = is_sorted_until(a.begin(), a.end());

来自cppreference的描述：

Examines the range [first, last) and finds the largest range beginning at first in which the elements are sorted in ascending order.

要获得两种旋转方式的最小值，请使用

min(a.front(), *is_sorted_until(a.begin(), a.end()))

这小于 O(n) 但不是 O(log n)。

EDIT 由于您链接了 SO 线程，我正在翻译 C++

中的答案

int findMin(vector<int> & arr) {
    int low = 0;
    int high = arr.size() - 1;
    while (arr[low] > arr[high]) {
        int mid = (low + high) >> 1;
        if (arr[mid] > arr[high])
            low = mid + 1;
        else
            high = mid;
    }
    return arr[low];
}

查看它在 http://ideone.com/BlzrWj 的工作情况。

Answer 3

这有一股赋值的味道，所以没有标准库。

我的切割是通过寻找不连续点来找到轴心点：

int findpivot(vector<int> a)
{
    int left = 0;
    int right = a.size() - 1;

    while (a[left] > a[right])
    {
        int mid = (right + left) / 2;
        if (a[mid] > a[right])
        { 
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return left;
}

然后我会查看枢轴两侧的第一个值以获得最低值。运行该函数发现（事后看来，"Duh!"）它总是 return 编辑最低值的索引，因为我在枢轴处寻找不连续性的方式。

最终结果与 Java 解决方案相同，除了我 return 枢轴点和 Java 解决方案 returned 枢轴处的值点.

关于第二个问题，为什么OP被否决了？ OP没有被否决。 OP的问题是。

好的，为什么 OP 的问题被否决了？

我能想到的最佳答案是这个问题是重复的。 OP 发现了重复项，但没有正确实施。这限制了这个问题对未来提问者的用处。

Answer 4

试试这个：

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;
int findMinInRotatedSortedVec(vector<int>v, int start, int end)
{
    if (start == end) return v[start];
    int mid = (end-start)/2+start;
    if (v[start] == v[mid]) {
        if (v[mid] == v[end]) {
            int min1 = findMinInRotatedSortedVec(v, start, mid);
            int min2 = findMinInRotatedSortedVec(v, mid+1, end);
            return (min1 > min2) ? min2 : min1;
        }
        if (v[mid] < v[end]) return v[start];
    }
    if ((v[start] < v[mid]) && (v[mid] <= v[end])) return v[start];
    if (v[start] > v[mid]) return findMinInRotatedSortedVec(v, start, mid);
    return findMinInRotatedSortedVec(v, mid+1, end);
}

int main() {
    vector<int> v (70);
    std::iota(v.begin(), v.end(), 31);
    rotate(v.begin(),v.begin()+43,v.end());
    cout <<"Min is " << findMinInRotatedSortedVec(v,0,v.size()-1) <<endl;
  return 0;
}

Answer 5

你有正确的策略，但没有想清楚不变量。

我假设元素是不同的。没有这个，它不能在 O(log n) 时间内完成。（考虑除单个 1 外所有元素均为 0 的情况。）

如果a[0] < a[size-1]，则没有有效轮换，所以a[0]是最小

否则有两个递增的运行a[0]<a[1]<...<a[k-1]和a[k]<a[k+1]<...<a[size-1]，这里我们也知道a[k-1]>a[k]。

我们想找到k。

开始 - 就像你所做的那样 - 使用括号 [0, size-1] 的猜测。

不变量是这个括号必须总是包含k。当然，这对于初始支架是正确的！

为确保终止，我们必须在每次迭代期间将其变小。当区间只有一个元素时，即lo == hi，我们就有了答案。

如您所展示的那样计算新的猜测，

int mid = (lo + hi) / 2;

现在，有哪些可能性？ Mid 位于 [0, k-1] 或 [k, size-1] 中。

如果是前者，则我们知道mid <= k-1。我们可以在保持不变的情况下使括号 [mid+1, hi] 。请注意，这总是使支架变小，确保终止。

如果是后者，我们知道mid >= k，所以可以用[lo, mid]。注意我们不能说[lo, mid-1]因为mid 可能等于k，打破不变量。

这引发了另一个问题。如果 mid 的计算产生 mid == hi，则新括号与旧括号相同。我们将没有进展和无限循环。幸运的是，这永远不会发生，因为 (lo + hi) / 2 < hi 每当 lo < hi.

最后一块拼图是如何判断运行 mid 位于哪个位置。这很容易。如果 a[mid] >= a[0]，我们知道它位于第一个运行。否则它位于第二个。

用代码包装所有这些：

if (a[0] < a[size - 1]) return 0;
int lo = 0, hi = size - 1;
while (lo < hi) {
  int mid = (lo + hi) / 2;
  if (a[mid] >= a[0])
    lo = mid + 1;
  else
    hi = mid;
}
return lo;

在旋转数组中查找最小值

Find Min in Rotated Array

c++

algorithm

stl

vector

binary-search