二分查找入门——第3天

• 前言
• 一、367. 有效的完全平方数
• • 1.题目
  • 2.链接
  • 3.思路
  • 4.题解
  • 5.结果
• 二、1385. 两个数组间的距离值
• • 1.题目
  • 2.链接
  • 3.思路
  • 4.题解
  • 5.结果
• 总结

通过力扣（LeetCode）的两道例题来进一步加深二分查找

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

利用二分查找，从0~ num / 2 中间查找，如果满足(num+0.0)/mid == mid,则返回true，如果不满足,则判断大小,继续用二分查找,直到找到或查找完成为止。
注意：判断条件使用mid*mid == num时,应该用long类型。因为int类型会导致溢出。

代码如下（示例）：

class Solution {
    public boolean isPerfectSquare(int num) {
        if(num <= 2)
            return true;
        int left = 0;
     	//这里应该可以优化一下，使查找范围更小一点。
        int right = num/2;
        while(left <= right){
            int mid = left + (right - left)/2;
            if((num+0.0)/mid == mid){
                return true;
            }
            if(mid > (num+0.0)/mid){
                right = mid - 1;
            }
            if(mid < (num+0.0)/mid){
                left = mid + 1;
            }
        }
        return false;
    }
}

https://leetcode.cn/problems/find-the-distance-value-between-two-arrays/

先将arr2排序,在遍历arr1,利用二分查找,查找arr1中的值是否满足题目要求。
写一个函数判断一下，该函数从arr2的中间的值查找(mid),如果arr2[mid] 满足 |arr1[i]-arr2[mid]| <= d 返回false，如果不满足，且arr2[mid]>arr1[i],则在右半部查找,反之,就在左边部查找。如果没有找到,则返回true。

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int count = 0;
        for(int i : arr1){
            if(rank(arr2, i, 0, arr2.length-1, d)){
                count++;
            }
        }
        return count++;
    }
    //key则为arr1[i]
    public boolean rank(int[] arr2,int key ,int lo, int hi, int d){
        if(hi
            return true;
        }
        int mid = lo + (hi-lo) / 2;
        if(Math.abs(arr2[mid]-key) <= d){
            return false;
        }
        if(arr2[mid] > key){
            return rank(arr2, key, lo, mid-1, d);
        }
        if(arr2[mid] < key){
            return rank(arr2, key, mid+1, hi, d);
        }
        return true;
    }
}

其实二分查找并不一定要从正中间开始分,而是尽量找到一个更接近我们要找的那个数字的地方，这样能够减少很多查找次数。