在已移动的排序数组中找到最小值

Question

面试问题：已排序的数组已旋转，因此元素可能以 3456712 的顺序出现。如何找到最小元素？您可以假设该数组具有所有唯一元素

需要实现修改后的二分查找算法。 C++ 中的第一个（不正确的解决方案）：

int findMin(int a[], unsigned int leftIndex, unsigned int rightIndex)
{
    while(leftIndex <= rightIndex)
    {
        unsigned int mid = leftIndex + (rightIndex - leftIndex) / 2;
        if(leftIndex  == rightIndex) return a[rightIndex];
        if(a[rightIndex] > a[mid] && a[leftIndex] > a[mid]) 
        {
            ++leftIndex; 
            rightIndex = mid;
        }
        if(a[rightIndex] > a[mid]) rightIndex = --mid;
        if(a[rightIndex] < a[mid]) leftIndex = ++mid;
    }
}

Java 中的第二个实现是在已移动的排序数组中查找最小值。它通过了单元测试。如果您在 Java 实施中发现错误，请告诉我。

class Test
{
    static public int findMin(int a[], int leftIndex, int rightIndex)
    {
        while(leftIndex <= rightIndex)
        {
            int mid = leftIndex + (rightIndex - leftIndex) / 2;

            if(leftIndex == rightIndex) return a[rightIndex];
            if(rightIndex - leftIndex == 1) return Math.min(a[leftIndex], a[rightIndex]);
            if(a[rightIndex] > a[mid]) rightIndex = mid;
            if(a[rightIndex] < a[mid]) leftIndex =  mid;
        }
        return -1;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        int a1 [] = {1};
        System.out.println(findMin(a1,0,0));

        int a2 [] = {1,2};
        int a3 [] = {2, 1};
        System.out.println(findMin(a2,0,1));
        System.out.println(findMin(a3,0,1));

        int a4 [] = {1, 2, 3};
        int a5 [] = {2, 3, 1};
        int a6 [] = {3, 1, 2};
        System.out.println(findMin(a4,0,2));
        System.out.println(findMin(a5,0,2));
        System.out.println(findMin(a6,0,2));

        int a7 [] = {1, 2, 3, 4};
        int a8 [] = {2, 3, 4, 1};
        int a9 [] = {3, 4, 1, 2};
        int a10 [] = {4, 1, 2, 3};
        System.out.println(findMin(a7,0,3));
        System.out.println(findMin(a8,0,3));
        System.out.println(findMin(a9,0,3));
        System.out.println(findMin(a10,0,3));
    }
}

Java中的递归实现：

static public int findMin(int a[], int leftIndex, int rightIndex)
    {
            int mid = leftIndex + (rightIndex - leftIndex) / 2;
            if(leftIndex == rightIndex) return a[rightIndex];
            if(rightIndex - leftIndex == 1) return Math.min(a[leftIndex], a[rightIndex]);
            if(a[rightIndex] > a[mid]) return findMin(a, leftIndex, mid);
            if(a[rightIndex] < a[mid]) return findMin(a, mid, rightIndex);
            return -1;
    }

Answer 1

没有。不幸的是，代码并不正确。我做了一个简单的测试，程序没有return（无限循环）。

我注意到的一些问题：

unsigned int mid = leftIndex + (leftIndex + rightIndex) / 2;

你想要介于两者之间。那你为什么要添加 leftIndex?

然后

if(a[rightIndex] < a[mid]) leftIndex = ++mid;

为什么++mid？那么

if(a[rightIndex] > a[mid] && a[leftIndex] > a[mid]) 
        {
            ++leftIndex; 
            rightIndex = mid;
        }

我没有想通，但是我觉得这个案子不应该是一个单独的案子。那么

if(a[rightIndex] > a[mid]) rightIndex = mid;

应该是 >= 而不仅仅是 >（考虑重复值）。

你想实现的大概思路是：

If leftIndex val is smaller than mid, then leftIndex=mid.
If rightIndex val is larger than mid, then rightIndex=mid.
When the indices meet (or are neighbours of each other) you found the min.

现在自己试试吧。只有当你自己没有正确理解时，你才应该继续阅读。

我稍微调整了你的代码使其工作：

int findMin(int a[], unsigned int leftIndex, unsigned int rightIndex)
{
    if(a[leftIndex] < a[rightIndex]){
      //then the array is perfectly sorted (i.e. shifted k*size_of_array for any integer k) 
      //hence we return the first element.
      return a[leftIndex];
    }
    while(leftIndex <= rightIndex)
    {
        unsigned int mid = leftIndex + (rightIndex - leftIndex) / 2;
        if((leftIndex  == rightIndex) || (leftIndex+1 == rightIndex))
        {
         return a[rightIndex];
        }
        if(a[leftIndex] <= a[mid]) leftIndex = mid;
        if(a[rightIndex] >= a[mid]) rightIndex = mid;
    }
}

注1：我还没有完全测试这段代码。所以它可能不是防弹的。但它适用于一些简单的例子。当我有更多时间的时候，我可能会测试一些 cornercases。

注2：可以进一步清理代码。但我仍想靠近您的代码段。

在已移动的排序数组中找到最小值

Find minimum in sorted array, which was shifted

c++

arrays

binary-search