first_and_last_in_sorted_array

first_and_last_in_sorted_array.go 源码

package leetcode

/ 在排序数组中查找元素的第一个和最后一个位置

/ 直接遍历查找
func searchRange1(nums []int, target int) []int {
	j := -1
	for i, v := range nums {
		if v == target {
			j = i
			break
		}
	}
	k := j
	for i := j + 1; i < len(nums) && nums[i] == target; i++ {
		k = i
	}
	return []int{j, k}
}

/ 遍历查找，另一种写法
func searchRange3(nums []int, target int) []int {
	res := []int{-1, -1}
	for i, v := range nums {
		if v == target {
			if i == 0 || nums[i-1] != target {
				res[0] = i
			}
			if i == len(nums)-1 || nums[i+1] != target {
				res[1] = i
			}
		}
	}
	return res
}

/ 二分查找
func searchRange2(nums []int, target int) []int {
	lo, hi := 0, len(nums)-1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		if nums[mid] > target {
			hi = mid - 1
		} else if nums[mid] < target {
			lo = mid + 1
		} else {
			if nums[lo] == target && nums[hi] == target {
				return []int{lo, hi}
			}
			if nums[lo] != target {
				lo++
			}
			if nums[hi] != target {
				hi--
			}
		}
	}
	return []int{-1, -1}
}

你可能感兴趣的文章

first_bad_version

min_in_rotated_sorted_array

minimum_genetic_mutation