給你一個(gè)整數(shù)數(shù)組 nums ，和一個(gè)整數(shù) target 。

該整數(shù)數(shù)組原本是按升序排列，但輸入時(shí)在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。（例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] ）。

請(qǐng)你在數(shù)組中搜索 target ，如果數(shù)組中存在這個(gè)目標(biāo)值，則返回它的索引，否則返回 -1 。

示例 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

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array

解題思路

采用二分法的思想, 并結(jié)合旋轉(zhuǎn)數(shù)組的特性, 在[left, mid]和[mid, right]中找出哪一段是遞增的
并利用遞增的特性判斷目標(biāo)數(shù)是否在該遞增區(qū)間

• 每輪找出中間數(shù)值, 如果左端的數(shù)小于中間的數(shù), 則該[left, mid]是遞增區(qū)間
  • 如果目標(biāo)剛好在該遞增區(qū)間內(nèi), 則區(qū)間右端指針往中間移動(dòng)
  • 不在該區(qū)間內(nèi)則左端指針往中間移動(dòng)
• 另一種情況就是遞增區(qū)間在[mid, right]
  • 如果目標(biāo)剛好在該遞增區(qū)間內(nèi), 則區(qū)間左端指針往中間移動(dòng)
  • 不在該區(qū)間則右端指針往中間移動(dòng)
• 跳出循環(huán)后需要判斷左邊界的值是否等于目標(biāo)值, 因?yàn)檠h(huán)中更新查找區(qū)間時(shí)可能左右指針重疊然后跳出循環(huán), 如果指針?biāo)竸偤檬悄繕?biāo)值, 則需要單獨(dú)處理

代碼

class Solution {
    public int search(int[] nums, int target) {
        // 左右指針
        int i = 0, j = nums.length - 1;
        while (i < j) {
            // 中間指針
            int mid = (i + j) >> 1;
            // 中間數(shù)等于目標(biāo)時(shí)返回
            if (nums[mid] == target) {
                return mid;
            }
            // 如果左端的數(shù)小于中間的數(shù), 則該區(qū)間是遞增區(qū)間
            if (nums[i] <= nums[mid]) {
                // 如果目標(biāo)剛好在遞增區(qū)間內(nèi)
                if (nums[i] <= target && target < nums[mid]) {
                    // 區(qū)間右端往中間移動(dòng)
                    j = mid - 1;
                } else { // 不在遞增區(qū)間內(nèi)則左端往中間移動(dòng)
                    i = mid + 1;
                }
            } else { // 遞增區(qū)間在右邊
                // 如果目標(biāo)在遞增區(qū)間內(nèi)
                if (nums[mid] < target && target <= nums[j]) {
                    i = mid + 1;
                } else {
                    j = mid - 1;
                }
            }
        }
        return nums[i] == target ? i : -1;
    }
}