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

二分查找及相关题解析(Java)

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

二分查找及相关题解析(Java)

目录
  • 定义
  • 限制条件
  • 代码
  • 举一反三

定义

二分查找,又称折半查找法
基本思路:

找到有序序列的中位数mid,与目标值k进行比较,根据比较结果,进一步缩小查找范围。

限制条件
  • 必须是顺序表

    如果是链式存储,不能直接获取中间的数

  • 必须有序

    需要确定指针移动的方向,与中间值进行比较后,需要确定指针移动的方向。确保,一边比另一边大

  • 查找对象只能是一个
代码
public class BinarySearch {

    private static int[] nums = new int[]{0,1,2,3,4,4,4,5,6,7};

    public static void main(String[] args) {
        System.out.println(method1(nums,0));

        System.out.println(method2(nums,0));
    }

    
    private static int method1(int[] nums, int target){
        //定义指针
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){//循环条件,当相等时,也可能是最终结果
            int mid = (left+right)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                //mid 位置的值肯定不是目标值,所以--
                right = --mid;
            }else if(nums[mid] < target){
                //mid 位置的值肯定不是目标值,所以++
                left = ++mid;
            }
        }
        return -1;
    }

    
    private static int method2(int[] nums,int target){
        return recursion(nums, target, 0, nums.length-1);
    }

    private static int recursion(int[] nums, int target, int left, int right) {
        //退出条件
        if(left > right){
            return -1;
        }
        int mid = (left + right)/2;
        if(nums[mid] == target){
            return mid;
        }else if(nums[mid] > target){
            return recursion(nums,target,left,mid-1);
        }else{
            return recursion(nums,target,mid+1,right);
        }
    }
}

举一反三

当有序序列可重复,且需要寻找的元素在序列中有多个时,依据普通的二分查找,找到的元素是随机的。

问题1: 如何找到第一个出现的元素?

public class BinarySearch2 {

    private static int[] nums = {0,4,4,4,4,4,4,4,5};

    public static void main(String[] args) {
        System.out.println(method1(nums,4));
    }

    public static int method1(int[] nums, int target){

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

        while(left < right){
            int mid = (left + right) /2;
            //当中间值与目标值相等时,不能确定是不是第一个,但可以确定,数组右边一定不是,所以将右指针指向mid
            if(nums[mid] >= target){
            	//没有等号,因为中间值可能就是所需要的结果
                right = mid;
            }else{
                left = mid+1;
            }
        }
        //当left == right 的时候遍历完,只需要判断当前值是不是目标值即可
        if(nums[left] == target){
            return left;
        }

        return -1;
    }
}

问题2: 一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

来自leetcode 题目链接

分析:

  • 有序顺序表查找,可以使用二分查找。
  • 所有数字唯一,且只有一个不在数组中

    正常不缺失的数组,数组下标等于对应的值,
    当缺失了一个数字后,
    当前数字以及其后面的数字大于数组下标

public class BinarySearch3 {

    private static int[] nums = {0,1,2,3,4,6,7,8};

    public static void main(String[] args) {
        System.out.println(method1(nums));
    }

    private static int method1(int[] nums){

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

        if(nums[left] > left){
            return left;
        }

        return -1;
    }

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

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

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