二分查找
func search(nums []int, target int) int {
l, r := 0, len(nums) - 1
mid := 0
for l <=r { // = 是l 和r 相等的情况
mid = l + (r-l)>>1 // 防止溢出
if nums[mid] > target {
r = mid - 1 // 左半部分
} else if nums[mid] < target {
l = mid + 1 // 右半部分
} else {
return mid
}
}
return -1
}
在排序数组中查找元素的第一个和最后一个位置
https://leetcode.cn/leetbook/read/top-interview-questions-medium/xv4bbv/
func searchRange(nums []int, target int) []int {
result := make([]int,2)
result[0] = findFirst(nums, target)
result[1] = findLast(nums, target)
return result
}
func findFirst(nums []int, target int) int {
l, r := 0, len(nums) - 1
mid := 0
for l <= r {
mid = l + (r-l)>>1
if nums[mid] > target {
r = mid - 1
} else if nums[mid] < target {
l = mid + 1
} else {
if mid == 0 || nums[mid -1 ] != target {
return mid
} else {
r = mid - 1
}
}
}
return -1
}
func findLast(nums []int, target int) int {
l, r := 0, len(nums) - 1
last := r
mid := 0
for l <= r {
mid = l + (r-l)>>1
if nums[mid] > target {
r = mid - 1
} else if nums[mid] < target {
l = mid + 1
} else {
if mid == last || nums[mid + 1 ] != target {
return mid
} else {
l = mid + 1
}
}
}
return -1
}
func searchRangeV1(nums []int, target int) []int {
l,r := 0, len(nums) - 1
index := findIndex(nums, l, r , target)
if index == -1 {
return []int{-1,-1}
}
lindex,rindex := index,index
for lindex > 0 {
if nums[lindex-1] == target {
lindex--
} else {
break
}
}
for rindex < r {
if nums[rindex+1] == target {
rindex++
} else {
break
}
}
if lindex <= rindex {
return []int{lindex,rindex}
}
return []int{-1,-1}
}
func findIndex(nums []int,l,r ,target int) int {
mid := 0
for l <= r {
mid = (r-l)/2+l
if nums[mid] > target {
r = mid - 1
} else if nums[mid] < target {
l = mid + 1
} else {
return mid
}
}
return -1
}
x 的平方根
func mySqrt(x int) int {
if x == 0 {
return 0
}
l , r := 1, x
mid := 0
for l <=r {
mid = l + (r-l)>>1
if mid <=x/mid { // 防止溢出
//看下一个
if (mid+1) <= x/(mid+1) {
l = mid + 1
} else {
return mid
}
} else {
r = mid - 1
}
}
return -1
}
搜索插入位置
func searchInsert(nums []int, target int) int {
l, r := 0, len(nums) -1
mid := 0
for l<=r {
mid = (r-l)>>1 + l
if nums[mid] >= target {
if mid == 0 || nums[mid-1] < target {
return mid
}
r = mid -1
} else {
l = mid + 1
}
}
return r + 1
}
- https://www.bilibili.com/video/BV1uv4y1s7xu/?spm_id_from=333.999.0.0&vd_source=82e03147a3c338ea1383309670651595
- https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solution/tian-jie-shuo-er-fen-cha-zhao-3zhong-fu-sqx34/
- https://www.bilibili.com/video/BV1uv4y1s7xu/?spm_id_from=333.999.0.0&vd_source=82e03147a3c338ea1383309670651595
