[数据结构与算法]二分查找核心思路解析与Leetcode相关题解（python，二分数值型）

二分查找的讲解请见上一篇文章。本文主要记录对数值进行二分的题目解法与思路。

374. 猜数字大小

class Solution:
    def guessNumber(self, n: int) -> int:
        left = 1
        right = n
        while left < right:
            mid = left + (right - left) // 2
            if guess(mid) == 1: # mid < pick
                left = mid + 1
            else:
                right = mid
        return left

正常二分思路。

702. 搜索长度未知的有序数组

class Solution:
    def search(self, reader, target):
        """
        :type reader: ArrayReader
        :type target: int
        :rtype: int
        """
        left, right = 0, 10000 # 英文官方有范围
        while left < right:
            mid = left + (right - left) // 2
            if reader.get(mid) < target:
                left = mid + 1
            else:
                right = mid
        
        return left if reader.get(left) == target else -1

基本思路一致，长度未知的情况下 right 设为最大值10000（英文官方的条件），然后二分查找，最后找到目标值则返回下标，没有则返回 -1。

287. 寻找重复数

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        left = 1
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2 
            cnt = 0 # 记录小于等于mid的元素个数
            for num in nums:
                if num <= mid:
                    cnt += 1
            if cnt > mid:
                right = mid
            else:
                left = mid + 1
        return left

这题给定一个包含 n + 1 个整数的数组，其数字都在 1 到 n 之间，只有一个数字是重复的。因此，对于某个数字 x 来说，正常来说小于等于 x 的数字应该有 x 个，例如有1、2、3、4共4个数字小于等于4，如果大于4了，则说明1、2、3、4其中有一个数字重复了，所以右边界左移，反之左边界右移。

69. x 的平方根

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        if x == 1:
            return 1

        left, right = 1, x // 2
        while left < right:
            mid = left + (right - left + 1) // 2
            if mid > x / mid: # mid的平方大于x就肯定不是平方根，等于一定是，小于可能是
                right = mid - 1
            else:
                left = mid
                
        return left

这题只能用分法二，因为题目要求直接舍弃小数部分，所以若平方根为分数，其两边的整数，我们应该取较小的一个，只有分法二符合条件，剩余两个元素时，需要 mid 指向 right，然后最后取值为 left。

367. 有效的完全平方数

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num == 1:
            return True

        left, right = 0, num // 2
        while left < right:
            mid = left + (right - left) // 2
            if mid < num / mid:
                left = mid + 1
            else:
                right = mid

        return True if left * left == num else False

比上一题简单一点，用分法一即可，不停寻找平方大于等于 num 的区间，得到第一个平方大于等于 num 的数字，若该数字平方正好是 num 则为平方根，否则不是。

1300. 转变数组后最接近目标值的数组和

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        s, n = 0, len(arr)
        for i in range(len(arr)):
            avg = (target - s) / (n - i)
            if avg < arr[i]: # 均值小于当前值arr[i]（以及后面的值），即value为均值可以让arr[i]到arr[n]的值变为均值
                return int(avg + 0.49)   #五舍六入，若为int(avg)会向下取整，直接截断
            s += arr[i]
        return arr[-1]

首先对数组进行排序，由小到大，然后我们思考，对于如[1, 2, 3, 4, 5]这样的数组，如果取value = 1，则数组为[1, 1, 1, 1, 1]，如果取value = 2，数组为[1, 2, 2, 2, 2]，即 value 的取值越大，数组和越大。因此，我们要让value从小到大，直到找到一个 value 使得数组和与 target 最为接近。

遍历数组，对于第i个元素，其之前的元素和为 s，剩下的元素如果能使得绝对值为0，一定等于(target - s) / (n - i) = avg，但是这个 avg 不一定出现在位置 i ，除非有 avg < arr[i]。

当位置i及其后面的元素可以变成avg时，如果出现 3.5 这种恰好在中间的数，无论取整为3或者4对于绝对值来说都是一样的，但是题目要求数尽量小，所以 3.5 应取整为3，而 3.51 就要取为4了，因此是五舍六入。int(avg)是直接截断，向下取整；int(avg + 0.5)是四舍五入；int(avg + 0.49)就是五舍六入。