算法之旅003 - 二分搜索Level1 Day3

跟着LeetCode的Study Plan重温一遍各种经典算法，本期是二分搜索算法Level1 Day3。

题目构成：Easy*2。

367. Valid Perfect Square

确定一个数是否是完全平方数，用二分搜索查找，代码(C++)如下：

    class Solution {
    public:
        bool isPerfectSquare(int num) {
            if (num==1)
                return true;
            int r{ 0 };
            int l{ num };
            long long int m{ num/2 };
            while (r <= l){
                long long int res = m * m;
                if (res == num)
                    return true;
                if (res > num)
                    l = m - 1;
                else
                    r = m + 1;
                m = (r+l)/2;
            }
            return false;
        }
    };

1385. Find the Distance Value Between Two Arrays

对于arr1中的任意一个数，它与arr2中的每一个数的差的绝对值要大于目标值，统计arr1中满足条件的元素个数，代码(Golang)如下：

    func abs1385(num int) int {
        if num >= 0 {
            return num
        }
        return -num
    }

    func findTheDistanceValue(arr1 []int, arr2 []int, d int) int {
        sort.Ints(arr2)
        le2 := len(arr2)
        helper := func(_num int) bool {
            i, j := 0, le2-1

            if arr2[0] >= _num {
                return arr2[0]-_num > d 
            }
            
            if arr2[j] <= _num {
                return _num - arr2[j] > d
            }

            for i <= j {
                k := (i + j) / 2
                v := arr2[k]
                if v == _num {
                    return false
                }
                if v < _num {
                    i = k + 1
                } else {
                    j = k - 1
                }
            }
    
            return abs1385(arr2[i]-_num) > d && abs1385(arr2[i-1]-_num) > d
        }

        r := 0
        for _, a := range arr1 {
            if helper(a) {
                r++
            }
        }
        return r
    }

这道题先把arr2排序，然后利用35. Search Insert Position的思路，判断arr1中的每一个数应该插入在arr2的哪个位置，然后只对比这个位置前后的两个数与插入的数的差就可以了。