题解 | NC48 在旋转过的有序数组中寻找目标值

package lib

func Search(nums []int, target int) int {
	// 先找到反转后的边界，然后在两个区间分别二分查找
	n := len(nums)
	sider := -1
	for i := 0; i < n-1; i++ {
		if nums[i] > nums[i+1] {
			sider = i
			break
		}
	}
	if sider == -1 {
		return BinarySearch(nums, target)
	}
	r1 := BinarySearch(nums[0:sider+1], target)
	r2 := BinarySearch(nums[sider+1:], target)
	switch {
	case r1 != -1:
		return r1
	case r2 != -1:
		return sider + r2 + 1
	default:
		return -1
	}
}

// 二分查找，返回target在序列中的位置，失败返回-1
func BinarySearch(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return -1
}

package lib

import "testing"

func TestSearch(t *testing.T) {
	type testCase struct {
		Nums   []int
		Target int
		Want   int
	}
	testGroup := map[string]testCase{
		"case1": {Nums: []int{6, 8, 10, 0, 2, 4}, Target: 10, Want: 2},
		"case2": {Nums: []int{2}, Target: 1, Want: -1},
		"case3": {Nums: []int{6, 8, 10, 0, 2, 4}, Target: 3, Want: -1},
		"case4": {Nums: []int{5, 1, 2, 3, 4}, Target: 5, Want: 0},
		"case5": {Nums: []int{6, 8, 10, 0, 2, 4}, Target: 2, Want: 4},
	}
	for info, v := range testGroup {
		t.Run(info, func(t *testing.T) {
			got := Search(v.Nums, v.Target)
			if got != v.Want {
				t.Errorf("expect: %v ,but got %v", v.Want, got)
			}
		})
	}
}