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
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