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
    
    

All Problems

All Solutions