力扣 33 搜索旋转排序数组

题意：给定一个有序无重复数组，数组被旋转移动了几个位置，在数组中找到指定的数

思路：

1. 设定首尾指针
2. 每次二分查找时确定一段有序的数组
3. 如果target在该区间，则更新首尾指针为该区间的index
4. 如果target不在该区间，则更新首尾指针为该区间以外的index
   具体思路可见代码注释

思想：二分查找

复杂度：时间O（lgn)，空间O(1)

class Solution {
    public int search(int[] nums, int target) {
        int l =0;
        int r = nums.length - 1;
        while(l<=r) {
            int m = l + (r-l)/2;
            // 中间的数即为target
            if(nums[m] == target)
                return m;
            // 数组从l到m是从小到大有序排列的
            else if(nums[l]<=nums[m]) {
                // target在l和m之间，前移r到m－1
                if(nums[l]<=target && nums[m] > target) {
                    r = m - 1;
                // target在m和r之间，后移l到m－1
                } else {
                    l = m + 1;
                }
            // 数组从m到r是从小到大有序排列的
            } else {
                 // target在m和r之间，后移l到m－1
                if(nums[m] < target && nums[r] >= target) {
                    l = m + 1;
                // target在l和m之间，前移r到m－1
                } else {
                    r = m - 1;
                }
            }
        }
        return -1;
    }
}