LeetCode-＞二分查找打卡(三)

有效的完全平方数

 public boolean isPerfectSquare(int num) {
        int left = 1;
        int right = num;
        while(left<=right){
            int middle = left+(right-left)/2;
            long tem = (long)middle*middle;
            if(tem==num){
                return true;
            }else if(tem>num){
                    right = middle-1;
            }else{
                    left = middle+1;
            }
        }
        return false;
    }

两个数组间的距离值

这道题的关键就在于->利用二分法在arr2中找到距离arr1[X]最相近的值,但是是要找的值是第一个大于等于arr1[x],并且,该值得前面的一个数是第一个小于等于arr1[x] 的值。

同时如果我们对于arr2进行排序之后，如果arr2的最后一个值表示的是小于arr1[x]那么就不需要比较了,

class Solution {
    //1     2   3   4
    //1     8   9   10
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int count = 0;
        for(int x : arr1){
            int index = binarySearch(arr2,x);
            boolean flag = true;
            if(index<arr2.length){
                flag&=arr2[index]-x>d;
            }
            if(index-1>=0 && index-1<arr2.length){
                flag &= x-arr2[index-1]>d;
            }
            count+=flag?1:0;
        }
        return count;
    }
    private int binarySearch(int[] array,int target){
    
        int left = 0;
        int right = array.length-1;
        while(left<right){
            int middle = left+(right-left)/2;
            if(array[middle]>target){
                right = middle;
            }else{
                left = middle+1;
            }
        }
        return left;
    }
}