当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.033.Search in Rotated Sorted Array

LeetCode.033.Search in Rotated Sorted Array


题目描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.


解题过程

这道题是153题寻找旋转有序数组的最小值的扩展,在旋转有序数组中查找指定值。还是low,high双指针二分搜索。
每次判断出单边有序后,就紧接着判断目标值是否在单边有序子数组中,从而可以一下子砍掉一半,实现O(logn)搜索

不过还是需要注意像{3,1}, {3,1,2}, {2,3,1}这样的容易出错的用例:

class Solution {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length-1;
        while(low<=high){
            int mid = (low+high)/2;
            if(nums[mid]==target)
                return mid;
            if(nums[mid]>=nums[low]){//左边有序,转折点在右边
                if(target>=nums[low] && target<nums[mid]){//target在左边
                    high = mid-1;
                }else{
                    low = mid+1;
                }
            }else{//右边有序,转折点在左边
                if(target>nums[mid] && target<=nums[high]){//target在右边
                    low = mid+1;
                }else{
                    high = mid-1;
                }
            }
        }
        return -1;
    }
}

找到最小值位置后转化为常规二分搜索

讨论区看到一个我比较喜欢的方法,先找到最小值的下标位置,然后确定目标值在哪个有序子数组中,从而转化为常规二分搜素:

public int search(int[] nums, int target) {
    int minIdx = findMinIdx(nums);
    if (target == nums[minIdx]) return minIdx;
    int m = nums.length;
    int start = (target <= nums[m - 1]) ? minIdx : 0;
    int end = (target > nums[m - 1]) ? minIdx : m - 1;

    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) return mid;
        else if (target > nums[mid]) start = mid + 1;
        else end = mid - 1;
    }
    return -1;
}

public int findMinIdx(int[] nums) {
    int start = 0, end = nums.length - 1;
    while (start < end) {
        int mid = start + (end -  start) / 2;
        if (nums[mid] > nums[end]) start = mid + 1;
        else end = mid;
    }
    return start;
}

GitHub代码


上一篇 MySQL-使用笔记

下一篇 LeetCode.153.Find Minimum in Rotated Sorted Array

阅读
488
阅读预计2分钟
创建日期 2018-03-02
修改日期 2018-03-03
类别
百度推荐