栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

0004力扣704题---二分查找

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

0004力扣704题---二分查找

704. 二分查找
给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示:

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。


方法一:二分查找

思路


定义左右两个指针,左指针开始时指向0,右指针指向末尾,即nums.length-1。再计算一个中间指针mid,它的值即左右指针的中点。
简单的计算方法为(left+right)/2 ,但是有可能左右指针相加会超过int类型的最大值,因此采用left + (right - left) / 2 的计算方法。
比较nums[mid]与target的值,若相等则直接返回mid,否则如果比target大,则右指针等于中间指针mid减一,否则左指针等于中间指针mid加一。

这个过程因该在循环中进行,当找到目标值时直接return返回,没有找到时,一直进行循环,直到left>right。此时即没有结果,返回-1

解题方法

    public int search(int[] nums, int target) {
        // 如果目标值存在返回下标,否则返回 -1
        // 在 [left, right] 区间里查找 target
        int left = 0, right = nums.length - 1;
        while (left <= right) { ///还有这里 要小于等于,要不然会报数组越界异常。
            int mid = left + (right - left) / 2;
        // 查询成功条件
            if (nums[mid] == target) {
        // 找到了,就将目标元素的索引返回
                return mid;
            } else if (nums[mid] > target) {
        // 下一轮搜索区间:[left, mid - 1]
                right = mid - 1;
            } else {
        // 此时:nums[mid] < target
        // 下一轮搜索区间:[mid + 1, right]
                left = mid + 1;
            }
        }
        return -1;
    }

用java实例来验证

public class Main {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;
        System.out.println(search(nums, target));
    }

    public static int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

输出:4

方法二:Java的Arrays.binarySearch()方法

需引入包:import java.util.Arrays;

解题方法
int index = Arrays.binarySearch(nums, target);


用java实例来验证

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;
        int index = Arrays.binarySearch(nums, target);
        if (index < 0) {
            System.out.println(-1);
        } else {
            System.out.println(index);
        }
    }
}

输出:4


方法三:递归处理

深化递归的思想,递归要有终止条件和子问题的解法。

示例:
 

public class Main {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;
        System.out.println(search(nums, target));
    }

    public static int search(int[] nums, int target) {
        return backtrack(0, nums.length - 1, nums, target);
    }

    private static int backtrack(int left, int right, int[] nums, int target) {
        // 先处理递归到底的情况
        if (left > right) {
        // 不能形成区间,返回 -1 表示没有找到
            return -1;
        }
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
        // 找到了,就将目标元素的索引返回
            return mid;
        }
        if (target > nums[mid]) {
// 既然是有序数组,目标元素的值比中间元素还要大,就应该在中间元素的右边去找
            return backtrack(mid + 1, right, nums, target);
        }
        if (target < nums[mid]) {
// 既然是有序数组,目标元素的值比中间元素还要小,就应该在中间元素的左边去找
            return backtrack(left, mid - 1, nums, target);
        }
        return -1;
    }
}

输出:4

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970969.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号