首页 > ACM题库 > LeetCode > Search in Rotated Sorted Array[LeetCode]二分查找
2014
09-01

Search in Rotated Sorted Array[LeetCode]二分查找

Search in Rotated Sorted Array

Suppose a sorted array 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.

题目链接:https://oj.leetcode.com/problems/search-in-rotated-sorted-array/

关于旋转数组问题在 无处不在的二分查找 一文里有提到,只不过那个问题是找到在哪个位置进行了旋转操作。

可以先找到旋转的位置,然后就可以把数组分为两个有序的部分,再分别进行两次二分查找即可。这种方法需要进行3次二分查找。

其实有更简单的方法,可以只进行一次二分查找。因为每一次都可以确定哪一半是有序的,再通过和这一半的最大值和最小值进行比较,就可以知道target位于哪一半。例如对于 4 5 6 7 0 1 2,设target=1 ,首先判断中间元素 A[mid=3] > A[0] 可以知道前面一半  4 5 6 (7) 是有序的,可以发现target肯定不位于这一半,直接排除掉即可。

//============================================================================
// Name        : SearchInRotated.java
// Author      : GaoTong
// Date        : 2014/9/1
// Copyright   : www.acmerblog.com
//============================================================================

public class SearchInRotated {
    public static int search(int[] A, int target) {
        return searchBinary(A, 0, A.length-1 , target);
    }

    public static int searchBinary(int A[],int s,int e,int target){
        int mid = (s+e)/2;

        if(A[mid] == target)
            return mid;
        if(s >= e) return -1;
        if( A[mid] < A[e] ){ //后半部分是顺序的
            if(target > A[mid] && target <= A[e]){
                return searchBinary(A, mid+1, e, target);
            }else
                return searchBinary(A, s, mid-1, target);
        }else{ //前半部分顺序的
            if(target >= A[s] && target < A[mid])
                return searchBinary(A, s, mid-1, target);
            else
                return searchBinary(A, mid+1, e, target);
        }

    }

    public static void main(String args[]){
        int arr[] = {4 ,5 ,6, 7 ,0, 1, 2};
        System.out.println(search(arr, 1));
    }
}

Search in Rotated Sorted Array II

对于有重复的,上面的方法就不适用了。这里用了一个简便的方法,对于无法判断的直接循环遍历。

public class Solution {
    public static boolean search(int[] A, int target) {
        return searchBinary(A, 0, A.length-1 , target);
    }

    public static boolean searchBinary(int A[],int s,int e,int target){
        int mid = (s+e)/2;

        if(A[mid] == target)
            return true;
        if(s >= e) return false;
        if( A[mid] < A[e] ){ //后半部分是顺序的
            if(target > A[mid] && target <= A[e]){
                return searchBinary(A, mid+1, e, target);
            }else
                return searchBinary(A, s, mid-1, target);
        }else if(A[mid] > A[e]){ //前半部分顺序的
            if(target >= A[s] && target < A[mid])
                return searchBinary(A, s, mid-1, target);
            else
                return searchBinary(A, mid+1, e, target);
        }else{ //相等时,无法判断
            for(int i=s; i<=e; i++)
                if(A[i] == target) return true;
            return false;
        }

    }
}

  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.