二分查找原题 #

https://leetcode.cn/problems/binary-search/

注意计算mid的时候不要用(left+right) / 2，因为可能会溢出

func search(nums []int, target int) int {
    n := len(nums)

    left := 0
    right := n-1
    for left <= right {
        mid := left + ((right - left) / 2)
        if nums[mid] == target {
            return mid
        }

        if nums[mid] > target {
            right = mid-1
        } else {
            left = mid+1
        }
    }
    return -1
}

搜索插入位置 #

https://leetcode.cn/problems/search-insert-position/

1. 通过二分查找值
2. 插入位置默认为数组末尾，如果mid所在的数比target大，则更新插入位置为mid

func searchInsert(nums []int, target int) int {
    n := len(nums)
    left, right := 0, n-1
    ret := n

    for left <= right {
        mid := left + ((right - left) / 2)
        if nums[mid] == target {
            return mid
        }

		// 如果mid所在的数比target大，则更新插入位置为mid
        if nums[mid] > target {
            right = mid-1
            ret = mid
        } else {
            left = mid + 1
        }

    }
    return ret
}

查找元素出现的第一个和最后一个位置 #

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

1. 二分搜索找到第一个出现的位置
2. 二分搜索找到target+1出现的位置

func searchRange(nums []int, target int) []int {
    bs := func(tg int)int {
        l := 0
        r := len(nums)-1

        for l <= r {
            mid := l + (r-l)/2
            if nums[mid] >= tg {
                r = mid-1
            } else {
                l = mid+1
            }
        }
        return l
    }

    left := bs(target)
    right := bs(target+1)
    
    if left == len(nums) || nums[left] != target {
        return []int{-1,-1}
    }

    return []int{left, right-1}
}

平方根 #

https://leetcode.cn/problems/sqrtx/

1. 数<2时，平方根是它自己
2. 平方根< x/2，故只需要从0~x/2二分找即可
3. 当mid ^2 <= x 时，ret = mid

func mySqrt(x int) int {
    if x < 2 {
        return x
    }
    left, right := 0, x/2
    ret := -1
    for left <= right {
        mid := left + ((right - left) / 2)
        if mid * mid > x {
            right = mid - 1
        } else {
            ret = mid
            left = mid + 1
        }
    }
    return ret
}

完全平方数 #

https://leetcode.cn/problems/valid-perfect-square/

1. < 2的数是完全平方数
2. 数的平方根 < num / 2，所以只要从2 ～ num/2二分找即可

func isPerfectSquare(num int) bool {
    if num < 2 {
        return true
    }
    left, right := 2, num / 2
    for left <= right {
        mid := left + ((right - left) / 2)
        if mid * mid == num {
            return true
        } else if mid * mid > num {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return false
}