Question

Formatted question description: https://leetcode.ca/all/81.html

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

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.

@tag-array

Algorithm

Since the previous question Search in Rotated Sorted Array does not have the same value, when we compare the middle value and the rightmost value, we are in full compliance with the previous rule:

if the number in the middle is less than the rightmost number, the right half is in order.
If the number is greater than the rightmost number, the left half is ordered.

And if there can be repeated values, there will be two situations, [3 1 1] and [1 1 3 1]. For these two situations, when the intermediate value is equal to the rightmost value, the target value 3 can be either on the left or on the right.

It can be on the right, then what should we do? In this case, it is actually very simple. Just move the rightmost value to the left to continue the loop. If it is still the same, continue to move until it reaches a different value, and then the other parts are still Use the method in Search in Rotated Sorted Array

Code

Java

public class Search_in_Rotated_Sorted_Array_II {

    // time: O(1)
    // space: O(N)
	public class Solution {
	    public boolean search(int[] nums, int target) {

	        if (nums == null || nums.length == 0) {
	            return false;
	        }

	        int i = 0; // left pointer
	        int j = nums.length - 1; // right pointer

	        while(i <= j) {
	            int mid = (i + j) / 2;

	            if (nums[mid] == target) {
	                return true;
	            }

	            // @note: if (nums[0] <= nums[mid]) {
	            if (nums[i] <= nums[mid]) { // left half ordered, right half not ordered

	                // if (target <= nums[mid]) {
	                if (nums[i] <= target && target <= nums[mid]) {
	                    j = mid;
	                } else {
	                    i++;
	                }
	            } else { // right half ordered, left half not ordered

	                // if (target <= nums[mid]) {
	                if (nums[mid] <= target && target <= nums[j]) {
	                    i = mid;
	                } else {
	                    j--;
	                }
	            }
	        }

	        return false;
	    }

	}
}

// OJ: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
// Time: average O(logN), worst O(N)
// Space: O(1)
class Solution {
    int findStart(vector<int> &A) {
        int L = 0, R = A.size() - 1;
        while (L + 1 < R) {
            if (A[L] < A[R]) return L;
            int M = (L + R) / 2;
            if (A[M] > A[R]) L = M + 1;
            else if (A[M] < A[R] || (A[M] == A[R] && A[L] > A[R])) R = M;
            else {
                int k = L;
                while (k < R && A[L] == A[k]) ++k;
                if (k == R) return L;
                if (A[k] < A[L]) return k;
                L = k + 1;
            }
        }
        return A[L] < A[R] ? L : R;
    }
public:
    bool search(vector<int>& A, int T) {
        if (A.empty()) return false;
        int start = findStart(A), N = A.size(), L = 0, R = N - 1;
        while (L <= R) {
            int M = (L + R) / 2, mid = (start + M) % N;
            if (A[mid] == T) return true;
            if (A[mid] < T) L = M + 1;
            else R = M - 1;
        }
        return false;
    }
};

class Solution(object):
  def search(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: bool
    """
    start, end = 0, len(nums) - 1
    while start + 1 < end:
      mid = start + (end - start) / 2
      if nums[mid] == target:
        return True
      if nums[start] < nums[mid]:
        if nums[start] <= target <= nums[mid]:
          end = mid
        else:
          start = mid
      elif nums[start] > nums[mid]:
        if nums[mid] <= target <= nums[end]:
          start = mid
        else:
          end = mid
      else:
        start += 1

    if nums[start] == target:
      return True
    if nums[end] == target:
      return True
    return False

81 - Search in Rotated Sorted Array II

Question

Algorithm

Code

All Problems

All Solutions