Skip to main content

34. Find First and Last Position of Element in Sorted Array

分析

二分经典题,好好体会 二分的 不会去除 答案区间

题解

func searchRange(nums []int, target int) []int {
left := findLeftBorder(nums, target)
right := findRightBorder(nums, target)
return []int{left, right}
}

/*
if target position exist -> idx
nums[idx] = target
*/

func findLeftBorder(nums []int, target int) int {
if len(nums) == 0 {
return -1
}
left, right := 0, len(nums) - 1
// [left, right]
for left < right {
mid := left + (right - left) >> 1
if nums[mid] < target {
left = mid + 1
} else {
right = mid
}
}

if nums[left] == target {
return left
}
return -1
}

func findRightBorder(nums []int, target int) int {
if len(nums) == 0 {
return -1
}

left, right := 0, len(nums) - 1
// [left, right]
for left < right {
mid := left + (right - left) >> 1 + 1
if nums[mid] > target {
right = mid - 1
} else {
left = mid
}
}

if nums[left] == target {
return left
}
return -1
}