代码随想录——二分查找(二)

模版

func binarySearch(nums []int, target int) int {
	l, r := 0, len(nums)-1
	for l <= r {
		mid := l + (r-l)/2
		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return -1
}

例题

一.第一个错误的版本

代码：

func firstBadVersion(n int) int {
    l,r:=1,n
    for l<r{
        mid:=(r-l)/2+l
        if isBadVersion(mid)==true{
            r=mid
        }else{
            l=mid+1
        }
    }
    return l
}

二.寻找峰值

代码：

func findPeakElement(nums []int) int {
    n:=len(nums)
    get:=func(i int) int{
         if i == -1 || i == n {
            return math.MinInt64
        }
        return nums[i]
    }
    l,r:=0,n-1
    for l<=r{
        mid:=(r-l)/2+l
        if get(mid)>get(mid-1)&&get(mid)>get(mid+1){
            return mid
        }else if get(mid+1)>get(mid){
            l=mid+1
        }else{
            r=mid-1
        }
    }
    return -1
}

解析：
这个可以参考二次函数的图像,当mid+1>mid时，说明还没有到图像的右半部分，这时候应该更新左半边界，mid-1<mid时，说明到了图像的右半部分，这时候要更新右边界。

三.寻找旋转排序数组中的最小值

代码：

func findMin(nums []int) int {
    n:=len(nums)
    l,r:=0,n-1
    for l<r{
        pivot:=(r-l)/2+l
        if nums[pivot] < nums[r] {
            r = pivot
        } else {
            l = pivot + 1
        }
    }
    return nums[l]
}