我对此进行了很多思考，但无法找到最佳解决方案。我正在准备技术面试，但我还没有找到太多与这个问题相关的东西。我的第一步是实现一个简单的 O(n) 算法，该算法搜索整个数组以找到最大整数。现在我知道我可以做得更好，所以我想也许有一种方法可以使用二分搜索或利用数组的至少一半已完全排序的事实。也许您可以找到中间值并将其与数组的开头和结尾进行比较。
示例：
[5, 7, 11, 1, 3] 将返回 11。
[7, 9, 15, 1, 3] 将返回 15。
在排序数组（甚至旋转）中，您可以确保使用二分搜索（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) 界限。观察最大元素右侧的元素是最小元素（如果数组根本没有旋转，则没有元素）。因此，进行常规二分搜索，但检查索引 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（因此您可以确定第一个和最后一个元素不是同一元素）。你必须自己尝试一下，如果有什么需要解决的话，就解决它。希望这有帮助。
在每一步中使用修改后的二分搜索消除一半已排序的子数组（如果有两个已排序的子数组，则删除“较低”的子数组），同时跟踪可能更新的最大值。
#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时，我们可以直接返回数组中的最大或最小元素。
情况2：当我们返回起始索引时，我们应该始终仔细检查它是否大于起始+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 #array
问题：找到旋转排序数组中最大的一个。该数组没有任何重复项： 解决方案：使用二分查找。 想法：永远记住，在排序旋转数组中，最大的元素始终位于数组的左侧。同样，最小的元素将始终位于数组的右侧。 代码是：
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] ;
}```
这是二分查找的实现 - O(log(n))
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 (mid == nums.length-1 || nums[mid] > nums[mid+1] || nums[left] == nums[mid]){
return nums[mid];
} else if (nums[left] < nums[mid]) {
left = mid + 1;
} else if (nums[left] > nums[mid]){
right = mid - 1;
}
}
return -1;
}
这个问题用另一个版本的二分查找就很简单了：
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];
}