二分查找学习

二分查找

适用于有序数组，题目条件可以转化为一个恒不等式

【最小化最大值】也是二分查找的标志

排序用sort.Ints

二分查找都是实现找一个≥目标值的数

大于⇒大于等于target+1

小于⇒大于等于target-1

小于等于⇒大于target-1

go里sort.SearchInts(nums,target)返回的就是大于等于target的数的位置

使用的时候需要考虑整除和不整除的问题

func erfen(nums []int,target int)int{
    left:=0
    right:=len(nums)-1
    for left<=right{
        mid:=left+(right-left)/2
        if nums[mid]<target{
            left=mid+1
        }else{
            right=mid-1
        }
    }
    return left
}
//[5,7,7,8,8,10]
//之后left=3,right=6,mid=4,nums[mid]==target
//然后left=3,right=3,mid=3,nums[mid]==target
//之后left=3,right=2,mid=2,这样写保证了最后返回的一定是找到的第一个target的位置

力扣 LeetCode2529. 正整数和负整数的最大计数 - 力扣（LeetCode）

//要始终记得，二分查找是【查找】，也就是找到对应元素及其位置
//所以这道题可以转化为，找到>=0的位置和>0的位置即可
//负数个数就是>=0位置，正数个数就是数组长度减去>0的位置
func lower_bound(nums []int,target int) int{
    n:=len(nums)
    left,right:=0,n-1
    for left<=right{
        mid:=left+(right-left)/2
        if nums[mid]<target{
            left=mid+1
        }else{
            right=mid-1
        }
    }
    return left
}

func maximumCount(nums []int) (ans int) {
    a:=lower_bound(nums,0)
    b:=lower_bound(nums,1)
    neg:=a
    pos:=len(nums)-b  
    return max(pos,neg)
}

//使用go自带函数的写法
func maximumCount(nums []int) int {
    neg := sort.SearchInts(nums, 0)
    // 第一个 > 0 的位置，等价于第一个 >= 1 的位置
    pos := len(nums) - sort.SearchInts(nums, 1)
    return max(neg, pos)
}

力扣 LeetCode875. 爱吃香蕉的珂珂 - 力扣（LeetCode）

这道题是对【答案】二分，如果k=0则不可能吃完，如果k=slices.Max(piles)，那么一定能吃完，则在这个范围内查找