題目

整數數組?nums?按升序排列，數組中的值?互不相同?。

在傳遞給函數之前，nums?在預先未知的某個下標?k（0 <= k < nums.length）上進行了?旋轉，使數組變為?[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標?從 0 開始?計數）。例如，?[0,1,2,4,5,6,7]?在下標?3?處經旋轉后可能變為?[4,5,6,7,0,1,2]?。

給你?旋轉后?的數組?nums?和一個整數?target?，如果?nums?中存在這個目標值?target?，則返回它的下標，否則返回?-1?。

你必須設計一個時間復雜度為?O(log n)?的算法解決此問題。

示例 1：

輸入：nums = [4,5,6,7,0,1,2], target = 0
輸出：4

示例?2：

輸入：nums = [4,5,6,7,0,1,2], target = 3
輸出：-1

示例 3：

輸入：nums = [1], target = 0
輸出：-1

題解

class Solution {public int search(int[] nums, int target) {int n = nums.length;if (n == 0) {return -1;}if (n == 1) { //先判斷以防進入死循環return nums[0]==target ? 0 : -1;}int left = 0, right = n - 1;while (left <= right) { //區間不為0int mid = left + (right - left)/2;if (nums[mid] == target) {return mid;}//本題mid 兩邊一邊遞增 另一邊不遞增if (nums[0] <= nums[mid]) { if (nums[0] <= target && target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}} else {if (nums[mid] < target && target <= nums[n - 1]) {left = mid + 1;} else {right = mid - 1;}}}return -1;}
}