搜索旋转数组

2021-01-02

面试题 10.03. 搜索旋转数组

难度中等46

搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。

示例1:

1 2	输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5 输出: 8（元素5在该数组中的索引）

示例2:

1 2	输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11 输出：-1 （没有找到）

提示:

arr 长度范围在[1, 1000000]之间

通过`nums[l]`与`nums[mid]`的比较来判断

如果左值小于中值，那么说明左边是递增的
- 如果左值小于等于target并且target小于等于中值：r = mid
- 否则 l = mid+1
如果左值大于中值，那么说明右边是递增的
- 如果左值小于等于target或者target小于等于中值: r = mid
- 否则l = mid +1
如果左值等于中值，那么说明有可能找到了目标
- 如果左值不等于target，那么l++
- 如果左值等于target，那么r=l

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        if (right == -1)
            return -1;
        while (left < right) {                                         // 循环结束条件left==right
            int mid = left + (right - left) / 2;                       // 防止溢出
            if (nums[left] < nums[mid]) {                              // 如果左值小于中值，说明左边区间升序               
                if (nums[left] <= target && target <= nums[mid]) {     // 如果目标在左边的升序区间中，右边界移动到mid
                    right = mid;                                       
                } else {                                               // 否则目标在右半边，左边界移动到mid+1
                    left = mid + 1;                                    
                }
            } else if (nums[left] > nums[mid]) {                       // 如果左值大于中值，说明左边不是升序，右半边升序
                if (nums[left] <= target || target <= nums[mid]) {     // 如果目标在左边，右边界移动到mid
                    right = mid;                                       
                } else {                                               // 否则目标在右半边，左边界移动到mid+1
                    left = mid + 1;                                    
                }
            } else if (nums[left] == nums[mid]) {                      // 如果左值等于中值，可能是已经找到了目标，也可能是遇到了重复值
                if (nums[left] != target) {                            // 如果左值不等于目标，说明还没找到，需要逐一清理重复值。
                    left++;
                } else {                                               // 如果左值等于目标，说明已经找到最左边的目标值 
                    right = left;                                      // 将右边界移动到left，循环结束
                }
            }
        }
        return (nums[left] == target) ? left : -1;                     // 返回left，或者-1
    }
}

数组的旋转就是循环移动，不管旋转多少次，一定是左边递增，中间断开，右边递增的

class Solution {
    public int search(int[] arr, int target) {
        int left = 0, right = arr.length - 1, mid = 0;

        while (left <= right) {
            mid = (left + right) / 2;

            if (arr[left] > arr[right] && arr[left] < arr[mid] && arr[mid] != target) {      // 左半边递增
                if (target < arr[mid] && target >= arr[left]) {                              // target在范围内
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else if (arr[left] < arr[right]) {                                            // 右半边递增

                if (target < arr[left] || target > arr[right]) return -1;
                if (target < arr[mid]) {
                    right = mid - 1;
                } else if (target > arr[mid]) {
                    left = mid + 1;
                } else {
                    int index = mid;
                    for (int i = mid; i >= 0; i--) {
                        if (arr[i] == arr[mid]) index = i;
                        else return index;
                    }
                }
            } else if (arr[left] == arr[mid] && arr[mid] != target) {
                for (int i = left; i < mid; i++) {
                    if (arr[i] == target) {
                        return i;
                    }
                }
                left = mid + 1;
            } else {                                                                        // 断点在中间
                if (target != arr[right]) {
                    right--;
                } else {
                    if (target == arr[0]) return 0;
                    if (target == arr[right]) {
                        int index = right;
                        for (int i = right; i >= 0; i--) {
                            if (arr[i] == arr[right]) index = i;
                            else return index;
                        }
                    }
                }
            }
        }

        return -1;
    }
}

高效优雅的题解

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        if (right == -1)
            return -1;
        while (left < right) {                                         // 循环结束条件left==right
            int mid = left + (right - left) / 2;                       // 防止溢出
            if (nums[left] < nums[mid]) {                              // 如果左值小于中值，说明左边区间升序               
                if (nums[left] <= target && target <= nums[mid]) {     // 如果目标在左边的升序区间中，右边界移动到mid
                    right = mid;                                       
                } else {                                               // 否则目标在右半边，左边界移动到mid+1
                    left = mid + 1;                                    
                }
            } else if (nums[left] > nums[mid]) {                       // 如果左值大于中值，说明左边不是升序，右半边升序
                if (nums[left] <= target || target <= nums[mid]) {     // 如果目标在左边，右边界移动到mid
                    right = mid;                                       
                } else {                                               // 否则目标在右半边，左边界移动到mid+1
                    left = mid + 1;                                    
                }
            } else if (nums[left] == nums[mid]) {                      // 如果左值等于中值，可能是已经找到了目标，也可能是遇到了重复值
                if (nums[left] != target) {                            // 如果左值不等于目标，说明还没找到，需要逐一清理重复值。
                    left++;
                } else {                                               // 如果左值等于目标，说明已经找到最左边的目标值 
                    right = left;                                      // 将右边界移动到left，循环结束
                }
            }
        }
        return (nums[left] == target) ? left : -1;                     // 返回left，或者-1
    }
}

作者：armeria-program
链接：https://leetcode-cn.com/problems/search-rotate-array-lcci/solution/er-fen-fa-by-armeria-program/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

作者：armeria-program来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

面试题 10.03. 搜索旋转数组

通过nums[l]与nums[mid]的比较来判断

数组的旋转就是循环移动，不管旋转多少次，一定是左边递增，中间断开，右边递增的

高效优雅的题解

通过`nums[l]`与`nums[mid]`的比较来判断