1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// @Title: 在排序数组中查找元素的第一个和最后一个位置 (Find First and Last Position of Element in Sorted Array)
// @Author: 15816537946@163.com
// @Date: 2020-06-25 07:15:36
// @Runtime: 8 ms
// @Memory: 4.1 MB
/*
 * @lc app=leetcode.cn id=34 lang=golang
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 *
 * https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
 *
 * algorithms
 * Medium (37.58%)
 * Likes:    217
 * Dislikes: 0
 * Total Accepted:    35.2K
 * Total Submissions: 93.3K
 * Testcase Example:  '[5,7,7,8,8,10]\n8'
 *
 * 给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *
 * 你的算法时间复杂度必须是 O(log n) 级别。
 *
 * 如果数组中不存在目标值,返回 [-1, -1]。
 *
 * 示例 1:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: [3,4]
 *
 * 示例 2:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: [-1,-1]
 *
 */


func searchRange(nums []int, target int) []int {
	first, last := -1, -1
	lo, hi := 0, len(nums)

	for lo < hi {
		mid := lo + (hi-lo)/2
		if nums[mid] == target {
			first, last = mid, mid
			break
		} else if nums[mid] > target {
			hi = mid
		} else {
			lo = mid + 1
		}
	}

	// 第一个索引
	for first > 0 && nums[first-1] == target {
		first--
	}
	// 最后一个索引
	for last < len(nums)-1 && nums[last+1] == target {
		last++
	}

	return []int{first, last}
}