长大后想做什么？做回小孩！

0%

LeetCode——搜索旋转排序数组

发表于 更新于 分类于 Valine：
本文字数： 305

NO.33 搜索旋转排序数组 中等

lr9fjf.png

根据题目的时间复杂度O(log n)，可以排除遍历的想法(遍历的时间复杂度O(n))，需要用二分查找。

思路一：二分法 二分查找一个很关键的点就是数组必须是有序的，本题的思路就是先找到有序的那一半，然后进行二分。思路的关键点就是找到有序的那一半，经过观察，数组中间元素左边部分或者右边部分必然有一半是有序的。

mid元素>start元素时左半部分是有序的；否则，右半部分是有序的。如果target不在有序的那半边，则继续二分，并且继续判断剩余部分元素的有序的一半(判断方法一样)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int search(int[] nums, int target) {
        if (nums==null||nums.length==0)return -1;
        int start=0,end=nums.length-1;
//        开始二分
        while (start<=end){
//            得到中间元素的下标
            int mid=start+(end-start)/2;
//            如果中间元素等于target，返回mid
            if (target==nums[mid])return mid;
//            如果中间元素大于第一个元素，说明前半部分是有序的,注意这里是>=
            if (nums[mid]>=nums[start]){
                if (target>=nums[start]&&target<nums[mid]){
                    end=mid-1;
                }else{
                    start=mid+1;
                }
            }else {//否则就是后半部分是有序的
                if (target<=nums[end]&&target>nums[mid]){
                    start=mid+1;
                }else {
                    end=mid-1;
                }
            }
        }
        return -1;
    }

时间复杂度：O(log n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github