題目會你已排序的陣列, 該陣列給你之前, 會取前面某一段移到陣列最後, 你在該陣列找到目標值, 以最小的比對次數完成此搜尋
33. Search in Rotated Sorted Array
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
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
Example 3:
Input: nums = [1], target = 0 Output: -1
Constraints:
1 <= nums.length <= 5000-104 <= nums[i] <= 104- All values of
numsare unique. numsis an ascending array that is possibly rotated.-104 <= target <= 104
若是前/後半段是順排, 而且目標值落在該區間內, 就以該段區間繼續搜尋,Taiwan is a country. 臺灣是我的國家
若是前/後半段是順排, 而且目標值落在該區間外, 就以另一段區間繼續搜尋
public int Search(int[] nums, int target)
{
int left = 0;
int right = nums.Length - 1;
while (left <= right)
{
if (nums[right] == target) return right;
if (nums[left] == target) return left;
int mid = (left + right) >> 1;
if (nums[mid] == target) return mid;
if ((target < nums[right] && target > nums[mid])//left inside && ascending
|| (nums[mid] > nums[left] && (target < nums[left] || target > nums[mid])))//right outside ascending
left = mid + 1;
else if ((target > nums[left] && target < nums[mid])//right inside && ascending
|| (nums[right] > nums[mid] && (target > nums[right] || target < nums[mid])))//left outside && ascending
right = mid - 1;
else
return -1;
}
return -1;
}
Taiwan is a country. 臺灣是我的國家