1、算法思路

題目要求必須設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為?O(log n)?的算法解決此問題，所以我們可以采用二分法。

Step1. 先把 nums[0] 作為目標(biāo)值，通過二分法找到旋轉(zhuǎn)點(diǎn)索引；

Step2. 如果旋轉(zhuǎn)點(diǎn)索引為0，則數(shù)組本身就是升序的，否則思想上可以將數(shù)組一分為二，看做兩個(gè)升序數(shù)組。

Step3. 判斷 target 目標(biāo)值在一分為二后的數(shù)組的哪一個(gè)里面，從而確定左右端索引。（特殊情況：如果旋轉(zhuǎn)點(diǎn)索引為0，則左右端索引就是 0 和 nums.length - 1）

Step4. 確認(rèn)了左右端索引之后，通過二分法查找到 target 值所在索引，若不存在則返回 -1。

2、Java代碼實(shí)現(xiàn)

public class Search {

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.search(new int[]{4,5,6,7,0,1,2}, 0));//4
        System.out.println(sol.search(new int[]{4,5,6,7,0,1,2}, 5));//1
        System.out.println(sol.search(new int[]{1,3,5,7,9}, 3));//1
        System.out.println(sol.search(new int[]{1,3}, 3));//1
        System.out.println(sol.search(new int[]{3,1}, 1));//1
        System.out.println(sol.search(new int[]{8,9,2,3,4}, 9));//1
        System.out.println(sol.search(new int[]{4,5,6,7,0,1,2}, 3));//-1
        System.out.println(sol.search(new int[]{1}, 0));//-1
        System.out.println(sol.search(new int[]{1,3}, 0));//-1
    }
}

// 逐一查找法
//class Solution {
//    public int search(int[] nums, int target) {
//        for (int i = 0; i < nums.length; i++) {
//            if(nums[i] == target){
//                return i;
//            }
//        }
//        return -1;
//    }
//}

// 二分查找法
class Solution {
    public int search(int[] nums, int target) {
        if (nums.length == 1){
            return nums[0] == target ? 0: -1;
        }
        // 尋找旋轉(zhuǎn)點(diǎn)的索引
        int l = 1;
        int r = nums.length - 1;
        while(l <= r){
            int mid = l + r >> 1;
            if(nums[mid] > nums[0]) l = ++mid;
            else r = --mid;
        }

        if(l > nums.length - 1){  //旋轉(zhuǎn)點(diǎn)為0時(shí)，數(shù)組依舊是升序排列的
            l = 0;
            r = nums.length - 1;
        }else if (target >= nums[0]){
            r = l - 1;
            l = 0;
        }else if(target <= nums[nums.length - 1]){
            r = nums.length - 1;
        }else return -1;  //target小于nums[0]又大于nums[n-1]時(shí)直接返回-1

        //target等于兩邊時(shí)直接返回索引
        if (nums[l] == target) return l;
        if (nums[r] == target) return r;

        // 最后進(jìn)行二分查找
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] == target) return mid;
            if(nums[mid] < target) l = ++mid;
            else r = --mid;
        }
        if(nums[l] != target) return -1;
        return l;
    }
}

3、完整題目

整數(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

示例?2：

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

示例 3：

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

提示：文章來源地址http://www.zghlxwxcb.cn/news/detail-742836.html

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums?中的每個(gè)值都?獨(dú)一無二
• 題目數(shù)據(jù)保證?nums?在預(yù)先未知的某個(gè)下標(biāo)上進(jìn)行了旋轉(zhuǎn)
• -10^4 <= target <= 10^4

到了這里，關(guān)于33. 搜索旋轉(zhuǎn)排序數(shù)組（二分法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！