Golang笔试之变异的二分查找

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [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])
		}
	}

}