There are several topics related to “Searching for a value in a rotated sorted array” in LeetCode. This is an extension of the topic related to “Finding the minimum value in a rotated sorted array”.
The core idea of solving the problem is: binary search.
The first questionSearch rotation sort array
Key words:
- Sorted in ascending order
- Different elements
- Return -1 if not found
In the code, I still consider repeating elements. First, there is no additional burden on running the code. Secondly, the solution of this problem and the solution of the next problem are unified.
Please refer to the comments for details. The reader should think more about the examples in the notes and exclude some sections by contradiction.
To sum up. There are four possibilities for analyzing an interval:
- The left element of the interval is less than the right element
- The left element of the interval is larger than the middle element
- The middle element is larger than the right element
- The left, middle, and right elements of the interval are equal
Take full advantage of what we know, narrow the search area as much as possible.
The solution is as follows (code submission approved)
func search(nums []int, target int) int {
l := len(nums)
if l == 0 {
return - 1
}
if l == 1 {
if nums[0] == target {
return 0
}
return - 1
}
var (
low int
high = l- 1
)
OuterLoop:
for low <= high {
// Middle position
mid := low + (high-low)>>1
v := nums[mid]
/ / found
if v == target {
return mid
}
// The left end of the interval is smaller than the right end of the element.
/ / as /..., 1, 2, 3, 4, 5,...
if nums[low] < nums[high] {
if v < target {
low = mid+1
} else {
high = mid- 1
}
continue
}
[...,5,6,7,1,2,3,4,...] , 5 > 1.
if nums[low] > v {
// Target may exist in index range (mid,high)
if target < nums[low] && v < target {
low = mid+1
} else { // Target may exist in index range [low, mid]
high = mid- 1
}
continue
}
// the middle element of the interval is larger than the right element, such as [...,2,3,4,5,6,7,1...]
if v > nums[high] {
// Target may exist in index range [low,mid]
if target < v && nums[high] < target {
high = mid- 1
} else { // Target may exist in index range (mid, high)
low = mid+1
}
continue
}
Nums [mid] == nums[high]
for i := low; i < high; i++ {
// A different value is encountered
// It could be one of the following
/ / /..., 9,5,6,9,9,9,9,9,9,...
/ / /..., 9,9,9,9,9,9,5,6,9,...
/ / /..., 9,10,11,9,9,9,9,9,9,...
/ / /..., 9,9,9,9,9,9,10,11,9,...
/ / /..., 9,10,2,9,9,9,9,9,9,...
/ / /..., 9,9,9,9,9,9,11,2,9,...
ifnums[i] ! = nums[i+1] {
low = i+1
if i+1 < mid {
// Index interval [low, I] and [mid,high] are equal, and not equal to target.
// just continue searching in index interval [I +1, mid-1].
high = mid- 1
} else { // I +1 > mid. I +1 == mid
// Index range [low, I] and index high are equal, and not equal to target.
// Just continue searching in index interval [I +1, high-1].
high--
}
continue OuterLoop
}
}
// The elements in the for loop above are all equal
/ / not found
break
}
return - 1
}
Copy the codeThe second questionSearch rotated sorted array II
Key words:
- In non-descending order
- Element values need not be different
- Returns true if found, false otherwise
This is definitely going to be a case of repeating elements. In this code, the logic is the same except that the return value is different, because the solution already takes into account repeating elements.
The solution is as follows (code submission approved)
func search(nums []int, target int) bool {
l := len(nums)
if l == 0 {
return false
}
var (
low int
high = l- 1
)
OuterLoop:
for low <= high {
mid := low + (high-low)>>1
v := nums[mid]
if v == target {
return true
}
if nums[low] < nums[high] {
if v < target {
low = mid+1
} else {
high = mid- 1
}
continue
}
if nums[low] > v {
if target < nums[low] && v < target {
low = mid+1
} else {
high = mid- 1
}
continue
}
if v > nums[high] {
if target < v && nums[high] < target {
high = mid- 1
} else {
low = mid+1
}
continue
}
for i := low; i < high; i++ {
ifnums[i] ! = nums[i+1] {
low = i+1
if i+1 < mid {
high = mid- 1
} else { // I +1 > mid. I +1 == mid
high--
}
continue OuterLoop
}
}
break
}
return false
}
Copy the codeThe third questionSearch rotation array
Key words:
- Sorted in ascending order
- There are duplicate elements
- To return the index. If there are multiple elements of the same type, the smallest index is returned. There is one more implicit detail, which returns -1 if not found.
The logic is similar to the first problem. I just made some adjustments for that problem.
The solution is as follows (code submission approved)
func search(arr []int, target int) int {
l := len(arr)
if l == 0 {
return - 1
}
var (
low int
high = l- 1
k = - 1
)
OuterLoop:
for low <= high {
mid := low + (high-low)>>1
v := arr[mid]
if v == target {
k = mid // Record the target index
}
if arr[low] < arr[high] {
// when v == target, try to find a smaller index
if v >= target {
high = mid- 1
} else { // v < target
low = mid+1
}
continue
}
if arr[low] > v {
if target < arr[low] && v < target {
low = mid+1
} else {
high = mid- 1
}
continue
}
if v > arr[high] {
if target < v && arr[high] < target {
high = mid- 1
} else {
low = mid+1
}
continue
}
if arr[low] == target {
// Low is the minimum index
k = low
break
}
for i := low; i < high; i++ {
ifarr[i] ! = arr[i+1] {
low = i+1
if i+1 < mid {
high = mid- 1
} else { // I +1 > mid. There is no I +1 == mid
high--
}
continue OuterLoop
}
}
// There is no need to look again
break
}
return k
}
Copy the code