Search in Rotated Sorted Array@LeetCode

LeetCode

Word count: 240 / Reading time: 1 min

 2015/03/30   Share

其实不太能理解为什么这题能标成hard，因为用很直观的算法便可以解出来。由于数组是被翻转过的，所以被分成两个部分，每个部分又都是有序的。所以先判断先判断一下要查找的数是在前半段还是后半段，然后依次查找即可。

public class Solution {
    public int search(int[] A, int target) {
        int index = -1;
        if (A == null || A.length == 0) return index;
        if (A[0] == target) return 0;
        if (A[A.length - 1] == target) return A.length - 1;
        int ALen = A.length;
        boolean hit = false;
        if (A[0] < target) {
            index = 1;
            while (index < ALen && A[index - 1] < A[index]) {
                if (A[index] == target) {
                    hit = true;
                    break;
                }
                index++;
            }
            if (!hit) {
                index = -1;
            }
        } else if (target < A[ALen - 1]){
            index = ALen - 2;
            while (0 <= index && A[index] < A[index + 1]) {
                if (A[index] == target) {
                    hit = true;
                    break;
                }
                index--;
            }
            if (!hit) {
                index = -1;
            }
        } else {
            index = -1;
        }
        return index;
    }
}

原文作者: findingsea

原文链接: http://findingsea.github.io/2015/03/30/search-in-rotated-sorted-array/

发表日期: March 30th 2015, 10:34:00 am

Next Post

Sudoku Solver@LeetCode
Previous Post

Permutations I II@LeetCode

CATALOG

