二分法求目标值范围

利用二分法求在非降序数组中距离目标值最近的两个数

Posted by Jae on February 22, 2019

要求

给一个没有重复元素的数组和目标值target,求距离该target最近的两个值,返回该距离(绝对值)

使用二分查找求目标值最近距离

定义两个指针lefthigh,并计算mid=left+(righ-left)/2,循环终止条件为left+1>=righ,循环终止说明目标值落在leftrigh指向的两个值之间即nums[left]<=target<=nums[righ].即找到了距离目标值最近的两个值

private int binarySearch(int[] nums, int target)
    {
        Arrays.sort(nums);

        int left = 0;
        int righ = nums.length - 1;

        while (left + 1 < righ)
        {
            int mid = left + (righ - left) / 2;

            if (nums[mid] == target)
            {
                return 0;
            }else if (nums[mid] < target)
            {
                left = mid;
            }else
            {
                righ = mid;
            }
        }

        return Math.min(Math.abs(target - nums[left]), Math.abs(target - nums[righ]));
    }