一、寻找一个数
1.左闭右闭
func search(nums []int, target int) int {
lf, rt := 0, len(nums)-1
for lf <= rt{
mid := lf + (rt-lf)/2
if nums[mid] < target{
lf = mid + 1
}else if nums[mid] > target{
rt = mid - 1
}else if nums[mid] == target{
return mid
}
}
return -1
}
2.左闭右开
func search(nums []int, target int) int {
lf, rt := 0, len(nums) // 左闭右开
// 不用等于为了避免lf=rt=len(nums)越界
for lf < rt{
mid := lf + (rt-lf)/2
if nums[mid] < target{
lf = mid + 1
}else if nums[mid] > target{
rt = mid // 区别
}else if nums[mid] == target{
return mid
}
}
// lf < len(nums)避免越界 如1,2,3,4中找8，此时lf=4越界
// nums[lf] == target lf==right这种情况漏了
if lf < len(nums) && nums[lf] == target{
return lf
}
return -1
}
二、寻找边界
常用左闭右开方法，该方法更好理解，不容易出错！
1.左闭右开
// 左边界 左闭右开
func leftBound(nums []int, target int) int {
if len(nums) == 0 {
return -1
}
lf, rt := 0, len(nums) // 左闭右开
for lf < rt {
mid := lf + (rt-lf)/2
if nums[mid] < target {
lf = mid + 1
} else if nums[mid] > target {
rt = mid
} else if nums[mid] == target {
rt = mid
}
}
// target比nums中的所有数都要大的时候 lf >= len(nums)
// 如果nums中不存在与target相等的数 但有小于target的数时会出现lf < len(nums) && nums[lf] != target
if lf < len(nums) && nums[lf] == target {
return lf
}
return -1
}
// 右边界 左闭右开
func rightBound(nums []int, target int) int {
if len(nums) == 0 {
return -1
}
lf, rt := 0, len(nums) // 左闭右开
for lf < rt {
mid := lf + (rt-lf)/2
if nums[mid] < target {
lf = mid + 1
} else if nums[mid] > target {
rt = mid
} else if nums[mid] == target {
lf = mid + 1
}
}
// target比nums中的左右数都要小的时候 lf-1 < 0
// 如果nums中不存在与target相等的数 但有小于target的数时会出现lf-1 >= 0 && nums[lf-1] != target
// 因为nums[mid] == target时lf=mid+1，所以结束循环时lf=右边界+1
if lf-1 >= 0 && nums[lf-1] == target {
return lf - 1
}
return -1
}
2.左闭右闭
越界现象
// 寻找左边界 左闭右闭
func leftBound(nums []int, target int) int {
lf, rt, mid := 0, len(nums)-1, 0
for lf <= rt {
mid = (lf + rt) >> 1
if target < nums[mid] {
rt = mid - 1
} else if target > nums[mid] {
lf = mid + 1
} else {
rt = mid - 1 // 右边界等于中间值--
}
}
if lf >= len(nums) || nums[lf] != target{
return -1
}
return lf
}
// 寻找右边界 左闭右闭
func rightBound(nums []int, target int) int {
lf, rt, mid := 0, len(nums)-1, 0
for lf <= rt {
mid = (lf + rt) >> 1
if target < nums[mid] {
rt = mid - 1
} else if target > nums[mid] {
lf = mid + 1
} else {
lf = mid + 1 // 左边界等于中间值++
}
}
if rt >= 0 && nums[rt] == target {
return rt
}
return -1
}