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

在旋转过的有序数组中寻找目标值

http://www.nowcoder.com/practice/87c0e7abcbda41e7963660fa7d020995

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

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 11:16
点赞 评论 收藏
分享
今天 11:05
门头沟学院 运营
点赞 评论 收藏
分享
点赞 评论 收藏
分享
06-23 11:43
门头沟学院 Java
allin校招的烤冷...:我靠,今天中午我也是这个hr隔一个星期发消息给我。问的问题还是一模一样的😅
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务