63.Search in Rotated Sorted Array II

1.Description(Medium)

Follow up for Search in Rotated Sorted Array:

What ifduplicatesare allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

Example

Given[1, 1, 0, 1, 1, 1]and target =0, returntrue. Given[1, 1, 1, 1, 1, 1]and target =0, returnfalse.

2.Code

Solution 1: Binary Search

Search in Rotated Sorted Array 在旋转有序数组中搜索

的延伸，现在数组中允许出现重复数字，这个也会影响我们选择哪半边继续搜索，由于之前那道题不存在相同值，我们在比较中间值和最右值时就完全符合之前所说的规律：

如果中间的数小于最右边的数，则右半段是有序的，若中间数大于最右边数，则左半段是有序的。

而如果可以有重复值，就会出现来面两种情况，[3 1 1] 和 [1 1 3 1]，对于这两种情况中间值等于最右值时，目标值3既可以在左边又可以在右边，那怎么办么，对于这种情况其实处理非常简单，只要把最右值向左一位即可继续循环，如果还相同则继续移，直到移到不同值为止，然后其他部分还采用Search in Rotated Sorted Array 在旋转有序数组中搜索中的方法

[l,m]为递增序列的假设就不能成立了，比如如下数据[1,3,1,1,1]

1. 对于每一个递增序列，遍历之，确认。

2. 找到pivot点，然后确定对应序列搜索。

如果A[m]>=A[l]不能确定递增，那就把它拆分成两个条件

1. A[m]>A[l] 递增

2. A[m] ==A[l] 确定不了，那就l++，往下看一步即可。

public boolean search(int[] A, int target) {
        if (A == null || A.length == 0) return false;
        int left = 0, right = A.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (A[mid] == target) return true;
            else if (A[mid] < A[right]) {
                if (A[mid] < target && A[right] >= target) left = mid + 1;
                else right = mid - 1;
            } else if (A[mid] > A[right]){
                if (A[left] <= target && A[mid] > target) right = mid - 1;
                else left = mid + 1;
            } else --right;
        }
        return false;
    }

Solution 2: 遍历

// 这个问题在面试中不会让实现完整程序

// 只需要举出能够最坏情况的数据是 [1,1,1,1... 1] 里有一个0即可。
// 在这种情况下是无法使用二分法的，复杂度是O(n)
// 因此写个for循环最坏也是O(n)，那就写个for循环就好了
//  如果你觉得，不是每个情况都是最坏情况，你想用二分法解决不是最坏情况的情况，那你就写一个二分吧。
//  反正面试考的不是你在这个题上会不会用二分法。这个题的考点是你想不想得到最坏情况。

public boolean search(int[] A, int target) {
        for (int i = 0; i < A.length; i ++) {
            if (A[i] == target) {
                return true;
            }
        }
        return false;
    }