关于java:牛客网高频算法题系列BM17二分查找I

30次阅读

共计 1027 个字符，预计需要花费 3 分钟才能阅读完成。

请实现无反复数字的升序数组的二分查找

给定一个元素升序的、无反复数字的整型数组 nums 和一个目标值 target，写一个函数搜寻 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1

原题目见：BM17 二分查找 -I

首先，思考非凡状况，判断如果数组为空，返回 -1。

否则，应用 low 和 high 别离为数组的上上限，而后应用二分法判断数组中的元素，判断过程如下：

首先，循环终止的条件是 low 大于 high

二分，mid 取两头值

如果 mid 所在的值等于 target，则返回 mid

如果 mid 所在的值大于 target，则更新 high

如果 mid 所在的值小于 target，则返回 low

最初，如果二分查找没找到等于 target 的值，返回 -1。

public class Bm017 {
    /**
     * 二分查找 -I
     *
     * @param nums   int 整型一维数组
     * @param target int 整型
     * @return int 整型
     */
    public static int search(int[] nums, int target) {
        // 如果数组为空，返回 -1
        if (nums == null || nums.length == 0) {return -1;}
        // low 和 high 别离为数组的上上限
        int low = 0, high = nums.length - 1;
        // 循环终止的条件是 low 大于 high
        while (low <= high) {
            // 二分，mid 取两头值
            int mid = (low + high) / 2;
            // 如果 mid 所在的值等于 target，则返回 mid
            // 如果 mid 所在的值大于 target，则更新 high
            // 如果 mid 所在的值小于 target，则返回 low
            if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {high = mid - 1;} else {low = mid + 1;}
        }

        // 如果二分查找没找到等于 target 的值，返回 -1
        return -1;
    }

    public static void main(String[] args) {int[] nums = {-1, 0, 3, 4, 6, 10, 13, 14};
        // 测试用例，冀望输入：6
        System.out.println(search(nums, 13));
    }
}