33. 搜索旋转排序数组

发表于 阅读次数： 本文字数： 765 阅读时长 ≈ 1 分钟

33. 搜索旋转排序数组

[4,5,6,7, 0,1,2]

将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.

判断条件可以由该图得出

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package leetcode.editor.cn.mycode.ID33;

import java.util.Arrays;

public class 搜索旋转排序数组 {
    class Solution {
        public int search(int[] nums, int target) {
            int n = nums.length;
            int l=0,r=n-1;
            while (l<=r)
            {     
                int mid=(l+r)/2;
                if(nums[mid]==target){
                    return mid;
                }
                //如果左边为有序
                if(nums[l]<=nums[mid])
                {
                    //利用左边有序判断是否在左边
                    if(nums[l]<=target&&nums[mid]>target)
                    {
                       r=mid-1;
                    }
                    else  l=mid+1;
                }
                else //右边有序
                {
                    //利用左边有序判断是否在左边
                    if (nums[mid] < target && nums[r] >= target) {
                        l = mid + 1;
                    } else r = mid - 1;
                }
            }
            return -1;
        }

    }

}