33. Search in Rotated Sorted Array
Problem:
6/19/2018 update:
If mid value is on upper part, it's easier to control going left. So that target has to on the upper part: target >= nums[left]. and target needs to be smaller than mid value, target < nums[mid]. Same thing applies to lower part.
The left and right points are inclusive. So add == to condition.
No need to use start + 1 < end template, since this problem finds the exact value.
01/16/2018 update
if (nums[start] < target < nums[mid]) move to left
if (nums[mid] < target < nums[end]) move to right
--------------------------------------------------------------------------------------------------------------------------
思路:
极端情况是target恰好是first 或者 last,如果判断的时候不加等号会被漏掉。target 和mid比较的时候没必要加等号。
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e.,
[0,1,2,4,5,6,7]
might become [4,5,6,7,0,1,2]
).
You are given a target value to search. If found in the array return its index, otherwise return
-1
.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2]
, target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2]
, target = 3
Output: -1
Analysis:6/19/2018 update:
If mid value is on upper part, it's easier to control going left. So that target has to on the upper part: target >= nums[left]. and target needs to be smaller than mid value, target < nums[mid]. Same thing applies to lower part.
The left and right points are inclusive. So add == to condition.
No need to use start + 1 < end template, since this problem finds the exact value.
class Solution { public int search(int[] nums, int target) { if (nums == null || nums.length == 0) return -1; int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; else if (nums[mid] >= nums[left]) { if (target < nums[mid] && target >= nums[left]) right = mid - 1; else left = mid + 1; } else { if (target > nums[mid] && target <= nums[right]) left = mid + 1; else right = mid - 1; } } return -1; } }_________________________________________________________________________________
01/16/2018 update
if (nums[start] < target < nums[mid]) move to left
if (nums[mid] < target < nums[end]) move to right
--------------------------------------------------------------------------------------------------------------------------
思路:
分成4个区间来考虑:
if(A[mid] > first)
{
if( target >= first && target < A[mid])
end = mid;
else
start = mid;
}
else if( A[mid] < last)
{
if(target <= last && target > A[mid])
start = mid;
else
end =mid;
}
实现:
极端情况是target恰好是first 或者 last,如果判断的时候不加等号会被漏掉。target 和mid比较的时候没必要加等号。
评论
发表评论