LeetCode------Search in Rotated Sorted Array
程序员文章站
2022-07-15 19:45:15
...
用题目中给的例子来分析,对于数组[0 1 2 4 5 6 7] 共有下列七种旋转方法:
二分搜索法的关键在于获得了中间数后,判断下面要搜索左半段还是右半段,观察上面数字,可以得出规律,如果中间的数大于或等于最左边的数,则左半段是有序的,若中间数小于最左边数,则右半段是有序的,我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内,这样就可以确定保留哪半边了,代码如下:
package com.zhumq.lianxi;
public class SearchinRotatedSortedArray {
// Search in Rotated Sorted Array
// Time Complexity: O(log n),Space Complexity: O(1)
public int search(int[] nums, int target) {
int first = 0, last = nums.length;
while (first != last) {
final int mid = first + (last - first) / 2;
if (nums[mid] == target)
return mid;
if (nums[first] <= nums[mid]) {
//中间数大于或等于最左边的数,则左半段有序
//首尾两个数组来判断目标值是否在左半区域内
if (nums[first] <= target && target < nums[mid])
last = mid;
else
first = mid + 1;
} else {
//中间数小于最左边的数,则右半段有序
//首尾两个数组来判断目标值是否在右半区域内
if (nums[mid] < target && target <= nums[last-1])
first = mid + 1;
else
last = mid;
}
}
return -1;
}
}
推荐阅读
-
【LeetCode】Two Sum & Two Sum II - Input array is sorted & Two Sum IV - Input is a BST
-
Convert Sorted Array to Binary Search Tree
-
【一天一道LeetCode】#26. Remove Duplicates from Sorted Array
-
167. Two Sum II - Input array is sorted [medium] (Python)
-
LeetCode 33. Search in Rotated Sorted Array && 81. Search in Rotated Sorted Array II
-
Leetcode 33 Search in Rotated Sorted Array
-
LeetCode·33. Search in Rotated Sorted Array
-
leetcode 33. Search in Rotated Sorted Array
-
0033_Search in Rotated Sorted Array
-
Search in Rotated Sorted Array II