在一个排序的数组（甚至是旋转的）中，你可以确保使用二分搜索（O（log2（n）））。

/**
* Time complexity: O(log2(n))
* Space complexity: O(1)
*
* @param nums
* @return
*/
public int findMax(int[] nums) {
        // binary search
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[left] < nums[mid]) {
                left = mid;
            } else if (nums[left] > nums[mid]) {
                right = mid - 1;
            } else {    
                // subtility here if there are duplicate elements in the array.
                // shift the left linearly
                left = left + 1;
            }
        }
        return nums[left];
    }

你必须以一种聪明的方式进行二分搜索，以实现O（lg n）界。观察max元素右边的元素是min（如果数组根本没有旋转，则为none）。所以做一个常规的二进制搜索，但检查索引mid处的元素是否是最大值，如果不是，则比较每个左/右子数组中的第一个和最后一个元素。如果first<last在左边的子数组中，你知道左边的子数组是排序的，然后向右，否则向左。
假设数组叫做a，它有n个元素。

/* check if not rotated at all */
int ans = INFINITY;
if(a[0] < a[n-1] || n == 1)
{   ans = a[n-1];
    return;
}

/* array is certainly rotated */
int l = 0, r = n-1;
while(r - l > 5)
{   int m = (l + r) / 2;
    if(a[m] > a[m+1]) { ans = a[m]; break; }
    else
    {   if(a[l] < a[m-1]) l = m+1;
        else r = m-1;
    }
}

/* check the remaining elements (at most 5) in a loop */
if(ans == INFINITY)
{   for(int i = l; i <= r; i++)
    {   ans = max(ans, a[i]);
    }
}

我没有测试过这个代码。当元素数为5或更少时，我中断的原因是要确保每个子数组中的元素数至少为2（因此可以确保first和last不是同一个元素）。你必须自己尝试，如果有什么需要修复的话，你必须修复它。希望这能帮上忙。

在每一步中，使用改进的二分搜索消除一半的排序子阵列（如果有两个排序子阵列，则删除“较低”的子阵列），同时跟踪潜在更新的最大值。

#include <iostream>
#include <cstdlib>
#include <vector>

int main(int argc, char** argv)
{   
    std::vector<int> nums;
    for(int i = 1; i < argc; i++)
        nums.push_back(atoi(argv[i]));

    int start = 0;
    int end = argc - 2;
    int max = nums[start];
    while(start <= end) {
        int mid = (start + end) >> 1;
        int cand;
        if(nums[start] <= nums[mid])  {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
        cand = nums[mid];
        if(cand > max)
           max = cand;
    }
    std::cout << max << std::endl;
    return 0;
}

Leetcode接受答案
条件-（数组已排序，已旋转）-
在一个长长度数组中搜索排序旋转数组中的最大元素有点容易，但我们必须考虑边缘情况，这是最大代码答案最终失败的原因。方法类似于二分搜索，但边缘情况不同
情况1：当数组的大小为2时。我们可以直接从数组中返回max或min元素。
情况2：当我们返回开始索引时，我们应该始终仔细检查它是否大于start+1元素，因为当我们返回开始索引时，我们通常会将其大小增加1，并且它返回的元素不是最大的。
此代码：

public static int findMax(int[] nums) {
        // binary search
        int start = 0;
        int end = nums.length - 1;
        // if array length is 2 then directly compare and return max element
        if(nums.length == 2){
            return nums[0] > nums[1] ? 0 : 1;
        }

        while (start < end) {
            // finding mid element
            int mid = start + (end - start) / 2;
            // checking if mid-element is greater than start
            // then start can become mid
            if (nums[start] < nums[mid]) {
                start = mid;
            }
            // checking if mid-element is smaller than start
            // then it can be ignored and end can become mid-1
            else if (nums[start] > nums[mid]) {
                end = mid - 1;
            }
            // now checking the edge case
            // we have start element which is neither smaller or greater than mid 
            // element
            // that means start index = mid-index
            // so we can increase start index by 1 if current start index is smaller 
            // that start +1
            // else the current start index is the max element
            else {
                if(nums[start]<=nums[start+1]) {
                    start = start + 1;
                }
                else {
                    return nums[start];
                }
            }
        }
        return nums[start];
    }

binarySearch #rotatedArray #sortedArray

问题：在旋转排序数组中查找largest。该数组没有任何重复项：解决方案：使用二进制搜索。想法：永远记住在排序旋转数组中，最大的元素总是在数组的左侧。同样，最小的元素将始终位于数组的右侧。代码为：

public class Test19 {

    public static void main(String[] args) {
        int[] a = { 5, 6, 1, 2, 3, 4 };
        System.out.println(findLargestElement(a));

    }

    private static int findLargestElement(int[] a) {

        int start = 0;
        int last = a.length - 1;

        while (start + 1 < last) {

            int mid = (last - start) / 2 + start;
            if (mid < start) {
                mid = start;
            }
            if (mid > start) {
                last = mid - 1;
            } else {
                mid--;
            }

        } // while

        if (a[start] > a[last]) {
            return a[start];
        } else
            return a[last];

    }

}

我提出的解决方案既紧凑又高效。它基本上是二进制搜索算法的副产品。

int maxFinder(int[] array, int start, int end)
  {
    //Compute the middle element
    int mid = (start + end) / 2;

    //return the first element if it's a single element array
    //OR
    //the boundary pair has been discovered.
    if(array.length == 1 || array[mid] > array[mid + 1])
    {return mid;}

    //Basic Binary Search implementation
    if(array[mid] < array[start])
    {return maxFinder(array, start, mid - 1);}
    else if(array[mid] > array[end])
    {return maxFinder(array, mid + 1, end);}

    //Return the last element if the array hasn't been rotated at all.
    else
    {return end;}
  }

所以，这个问题的时间复杂度是O（log2n）。我会做以下的事

#include<stdio.h>
#define ARRSIZE 200 
int greatestElement(int* , int ) ;

int main()  {
    int arr[ARRSIZE] ; 
    int n ; 
    printf("Enter the number of elements you want to enter in the array!") ;
    scanf("%d" , &n) ;
    printf("Enter the array elements\n") ;
    for(int i = 0 ; i < n ; i++)    {
        scanf("%d", &arr[i]) ;
    }
    printf("%d is the maximum element of the given array\n",greatestElement(arr,n)) ;
}

int greatestElement(int* arr, int n)    {
    int mid = 0 ;
    int start = 0 , end = n-1 ;
    while(start < end)  {
        mid = (start+end)/2 ;
        if(mid < n-1 && arr[mid] >= arr[mid+1]) {
            return arr[mid] ;
        }
        if(arr[start] > arr[mid])   {
            end = mid - 1 ;
        }
        else    {
            start = mid + 1; 
        }
    }
    return arr[start] ;
}```

这个问题在另一个版本的二进制搜索中很容易解决：

int solve(vector<int>& a) {
        int n = a.size();
        int k=0;
        for(int b=n/2; b>=1; b/=2)
        {
            while(k+b<n && a[k+b] >= a[0])
                k += b;
        }
        return a[k];
    }