搜索旋轉(zhuǎn)排序數(shù)組

整數(shù)數(shù)組 nums 按升序排列，數(shù)組中的值 互不相同 。

• 在傳遞給函數(shù)之前，nums 在預(yù)先未知的某個(gè)下標(biāo) k（0 <= k < nums.length）上進(jìn)行了 旋轉(zhuǎn)，使數(shù)組變?yōu)?[nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下標(biāo) 從 0 開始 計(jì)數(shù)）。例如， [0,1,2,4,5,6,7] 在下標(biāo) 3 處經(jīng)旋轉(zhuǎn)后可能變?yōu)?[4,5,6,7,0,1,2] 。

給你 旋轉(zhuǎn)后 的數(shù)組 nums 和一個(gè)整數(shù) target ，如果 nums 中存在這個(gè)目標(biāo)值 target ，則返回它的下標(biāo)，否則返回 -1 。

你必須設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為 O(log n) 的算法解決此問題。

示例 1：

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

解題思路

• 1、使用二分查找算法，在旋轉(zhuǎn)后的有序數(shù)組中查找目標(biāo)值。
• 2、根據(jù)二分查找的思想，不斷縮小搜索范圍，直到找到目標(biāo)值或者搜索范圍為空。
• 3、首先判斷當(dāng)前搜索范圍內(nèi)的數(shù)組部分是否是有序的：

•  如果是有序的，則直接在有序部分進(jìn)行二分查找；
  

•  如果不是有序的，則根據(jù)中間點(diǎn)位置，調(diào)整搜索范圍。
  

• 4、不斷循環(huán)以上步驟，直到找到目標(biāo)值或者搜索范圍為空。

思路：旋轉(zhuǎn)數(shù)組一定是一邊有序的，通過有序部分判斷查找范圍，不斷縮小查找范圍，直到找到元素

java實(shí)現(xiàn)

public class SearchRotatedSortedArray {public int search(int[] nums, int target) {//left 為數(shù)組的起始索引int left = 0;//右指針 right 為數(shù)組的結(jié)束索引int 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[left] && target < nums[mid]) {//數(shù)據(jù)就在左半部分，賦值right = mid-1right = mid - 1;} else {//數(shù)值不在左半部分，賦值left= mid+1left = mid + 1;}} else { // 右半部分有序（同上）if (target > nums[mid] && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;}}}return -1;}public static void main(String[] args) {SearchRotatedSortedArray searchRotatedSortedArray = new SearchRotatedSortedArray();int[] nums = {4,5,6,7,0,1,2};int target = 0;int result = searchRotatedSortedArray.search(nums, target);System.out.println("Index of target: " + result); // Output: 4}
}

時(shí)間空間復(fù)雜度

• 時(shí)間復(fù)雜度：O(log n)，其中n為數(shù)組nums的長(zhǎng)度。因?yàn)槭褂昧硕植檎宜惴ā?/p>

• 空間復(fù)雜度：O(1)。