假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
package main
import (
"fmt"
)
func main() {
iArray := []int{4, 5, 6, 7, 0, 1, 2}
var halfSearch func([]int, int, int, int) int
var unNormalHalfSearch func([]int, int, int, int) int
unNormalHalfSearch = func(arr []int, target, start, end int) int {
if start >= len(arr) || end >= len(arr) {
return -1
}
if start > end || (start == end && arr[start] != target) {
return -1
}
if arr[start] == target {
return start
}
if arr[end] == target {
return end
}
mid := (start+end)/2 + 1
if arr[mid] == target {
return mid
}
// [start,mid]是顺序的
if arr[start] < arr[mid] {
if arr[mid] < target {
return unNormalHalfSearch(arr, target, mid+1, end)
} else {
return halfSearch(arr, target, start, mid-1)
}
}
// [mid,end是顺序的]
if arr[mid] < target && arr[end] > target {
return halfSearch(arr, target, mid+1, end)
} else {
return unNormalHalfSearch(arr, target, start, mid-1)
}
return -1
}
halfSearch = func(arr []int, target, start, end int) int {
if start >= len(arr) || end >= len(arr) {
return -1
}
if start > end || (start == end && arr[start] != target) {
return -1
}
if arr[start] == target {
return start
}
if arr[end] == target {
return end
}
mid := (start+end)/2 + 1
if arr[mid] == target {
return mid
}
if target < arr[mid] {
return halfSearch(arr, target, start, mid-1)
}
return halfSearch(arr, target, mid+1, end)
}
testTarget := []int{4, 5, 0, 1, 2, 7, 3, 10}
testAns := []int{0, 1, 4, 5, 6, 3, -1, -1}
fmt.Printf("原始数组：%v\n", iArray)
for i := 0; i < len(testTarget); i++ {
index := unNormalHalfSearch(iArray, testTarget[i], 0, len(iArray)-1)
fmt.Printf("%d 所在的下标为：%d\n", testTarget[i], index)
if index != testAns[i] {
fmt.Errorf("%d 结果%d != 测试答案%d\n", testTarget[i], index, testAns[i])
}
}
}