Home Computer Science Java Algorithm

[[Lintcode problems]]
Algorithm: #binarysearch
Level: #medium
Time Complexity: #Ologn
Tags: #rotated
URL:62 · Search in Rotated Sorted Array - LintCode

# Description

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.
Example 1:

Input:

array = [4, 5, 1, 2, 3]
target = 1

Output:

2

Explanation:

1 is indexed at 2 in the array.
Example 2:

Input:

array = [4, 5, 1, 2, 3]
target = 0

Output:

-1

Explanation:

0 is not in the array. Returns -1.

Challenge:
O(logN) time

# Note

  1. 甚麼條件想到此算法的？

    • 因為 challenge 是 Ologn, 比 O (n) 快的算法就往二分法想。

  2. 甚麼是 rotated sorted array?**

    • 循環向左移

# 思路

  • [1,2,3,4,5,6,7] -> [5,6,7,1,2,3] 這樣的 array
    這樣就很明顯看出 5,6,7 是一段， 1,2,3 又是另一段
    假設我要找 target=2 的數

我知道我肯定得在 [1,2,3] 找，肉眼所看到，右邊的 [123] 比左邊的數都要少
那問題來了，我怎麼確認 1,2,3 的位置？

  • 我只需要知道左段的數比右邊的大 （並且知道是有序的）

在下面的代碼可以看到怎麼分這個情況（分出兩段）

1. 前段是有序的 (A [start] < A [mid]) e.g. [1,2,3,4,5,6]
那麼我就開始在這有序的 array 裡找 target，比如說 target = 5
if A[start] <= target && target <= A[mid]
這樣基本上確認了 target 就在 這一段有序的 array 裡面，
把 end = mid
else 那就代表不一定在這個範圍了，我們從 mid 後找
-> start = mid
2. else! 後一段的有序
同樣啦～找後面那段 [1,2,3]
java if A[mid] <= target && target <= A[end] start = mid! (從此段開始找) else end = mid

# Solution

public class Solution {
    /**
     * @param A: an integer rotated sorted array
     * @param target: an integer to be searched
     * @return: an integer
     */
    public int search(int[] A, int target) {
        if(A.length == 0 || A == null) {
            return -1;
        }
        int start = 0;
        int end = A.length - 1;
        int mid;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                return mid;
            }
            // 最開始的數 < mid : e.g [5,7,0] 這一段
                // mid = 7 , start = 5 
            if (A[start] < A[mid]) {
                if (A[start] <= target && target <= A[mid]){
                      end = mid; // 在 mid＝7 之後的不需要再看，
                } else {
                    start = mid; 
                }
            } else {
                if (A[mid] <= target && target <= A[end]) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        } // end while loop
        if (A[start] == target){
            return start;
        }
        if (A[end] == target) {
            return end;
        }
        return -1;
    }
}
[[63 Search in Rotated Sorted Array II]] 通常都是問完 正常版沒重覆的 rotated sorted array 後 再問這題的。 63 不能用二分
# Description
Follow up for Search in Rotated Sorted Array:
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
# Solution
// 这个问题在面试中不会让实现完整程序
    // 只需要举出能够最坏情况的数据是 [1,1,1,1... 1] 里有一个0即可。
    // 在这种情况下是无法使用二分法的，复杂度是O(n)
    // 因此写个for循环最坏也是O(n)，那就写个for循环就好了
    //  如果你觉得，不是每个情况都是最坏情况，你想用二分法解决不是最坏情况的情况，那你就写一个二分吧。
    //  反正面试考的不是你在这个题上会不会用二分法。这个题的考点是你想不想得到最坏情况。

public class Solution {
    /**
     * @param A: an integer ratated sorted array and duplicates are allowed
     * @param target: An integer
     * @return: a boolean 
     */
    public boolean search(int[] A, int target) {
        for (int i : A){
            if (i == target){
                return true;
            }
        }
        return false;
    }
}