蓝桥杯Java备战Day8——二分查找

新学笺

335人浏览 · 2026-03-08 15:29:47

新学笺 · 2026-03-08 15:29:47 发布

一、二分查找

1. 什么是二分查找？

二分查找（折半查找）：针对有序的数组 / 区间，每次通过中间值将查找范围缩小一半，直到找到目标值或确定目标值不存在，核心是 “折半缩范围”。

适用前提：数据必须有序；
核心优势：效率极高，数据量越大越明显；
核心难点：边界条件（左闭右开 / 左闭右闭）、中间值计算、循环终止条件。

2. 二分查找 2 种经典边界模型

最常用左闭右闭 [left, right] 模型（易理解、易书写），次用左闭右开 [left, right) 模型，固定一种模型写到底，不要混用！

模型 1：左闭右闭 [left, right]

范围定义：left 和 right 都在查找范围内，包含 nums [left] 和 nums [right]；
循环终止条件：left > right（范围无元素，查找失败）；
中间值计算：mid = left + (right - left) / 2（避免left+right int 溢出，比(left+right)/2更安全）；
范围收缩：
- 目标值 <nums [mid] → 目标在左半区，right = mid - 1（mid 已排除，无需再查）；
- 目标值 > nums [mid] → 目标在右半区，left = mid + 1（mid 已排除，无需再查）；
- 目标值 == nums [mid] → 找到目标，返回 mid。

模型 2：左闭右开 [left, right)

范围定义：left 在查找范围内，right 不在，仅包含 nums [left]，不包含 nums [right]；
循环终止条件：left == right（范围无元素，查找失败）；
中间值计算：mid = left + (right - left) / 2；
范围收缩：
- 目标值 <nums [mid] → 目标在左半区，right = mid（right 不在范围内，mid 无需 - 1）；
- 目标值 > nums [mid] → 目标在右半区，left = mid + 1；
- 目标值 == nums [mid] → 找到目标，返回 mid。

二、经典实战题

实战题 1：基础二分查找 - 有序数组找目标下标（左闭右闭模型）

题目要求

给定升序无重复数组nums = [-1,0,3,5,9,12]，查找目标值target，找到则返回其下标，未找到返回 - 1。

输入：target=9 → 输出：4；
输入：target=2 → 输出：-1。

核心模板

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums ={-1,0,3,5,9,12};
        int target1 =9;
        int target2 =2;
 
        int index1 = binarySearch(nums, target1);
        System.out.printf("目标%d的下标：%d\n", target1, index1);

        int index2 = binarySearch(nums, target2);
        System.out.printf("目标%d的下标：%d\n", target2, index2);
    }
    public static int binarySearch(int[] nums,int target){
        //二分查找的前提：有序
        Arrays.sort(nums);
        int left=0;
        int right=nums.length-1;

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

实战题 2：基础二分拓展 - 数的范围查询

题目要求

给定升序有重复数组nums = [1,2,2,2,3,4]，查找目标值2的第一个出现下标和最后一个出现下标。

输出：第一个下标 1，最后一个下标 3。

解题思路

找第一个出现下标：找到目标值后，不立即返回，继续向左半区收缩（right=mid-1），记录最后一次找到的下标；
找最后一个出现下标：找到目标值后，不立即返回，继续向右半区收缩（left=mid+1），记录最后一次找到的下标。

完整代码

public class Main {
    public static void main(String[] args) {
        int[] nums={1,2,2,2,3,4};
        int target=2;
        // 找第一个出现下标
        int firstIndex = findFirstIndex(nums, target);
        // 找最后一个出现下标
        int lastIndex = findLastIndex(nums, target);
        System.out.printf("目标%d的第一个出现下标：%d\n", target, firstIndex);
        System.out.printf("目标%d的最后一个出现下标：%d\n", target, lastIndex);
    }
    public static int findFirstIndex(int[] nums,int target){
        int left=0;
        int right=nums.length-1;
        int res=-1;//记录结果
        while (left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                res=mid;
                right=mid-1;
            } else if (nums[mid] > target) {
                right=mid-1;
            } else {
                left=mid+1;
            }
        }
        return res;
    }

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

实战题 3：二分答案 - 分割数组的最大值

题目要求

给定非负整数数组nums = [7,2,5,10,8]，将其分割为m=2个连续的子数组，使得每个子数组的和的最大值最小，求这个最小的最大值。

解题思路（二分答案核心）

确定答案范围：
- 最小值 left：数组中最大的单个元素（每个子数组至少包含一个元素，最大值不可能小于单个最大元素）→ 此处 left=10；
- 最大值 right：数组所有元素的和（分割为 1 个子数组，和为总和）→ 此处 right=7+2+5+10+8=32；
定义 check (mid) 函数：判断 “是否能将数组分割为不超过 m个子数组，且每个子数组的和≤mid”；
二分缩范围：若 check (mid) 为 true（可行），说明 mid 可以更小，向左半区收缩（找更小的最大值）；若为 false（不可行），说明 mid 需要更大，向右半区收缩；
循环结束后，left 即为答案（最小的最大值）。

完整代码

public class Main {
    public static void main(String[] args) {
        int[] nums ={7,2,5,10,8};
        int m =2; //分割为2个子数组
        int result =splitArray(nums, m);
        System.out.printf("分割为%d个子数组，和的最大值的最小值为：%d\n", m, result);
    }

    public static int splitArray(int[] nums,int m){
        int left=0;
        int right=0;
        for (int num : nums) {
            left=Math.max(num,left);
            right+=num;
        }

        while(left<=right){
            int mid=left+(right-left)/2;
            if(check(nums,m,mid)){
                right=mid-1;
            }
            else {
                left=mid+1;
            }
        }
        return left;
    }

    public static boolean check(int[] nums,int m,int mid){
        int count=1;//分割的子数组数，初始为1
        int currentSum=0;//当前子数组的和
        for (int num : nums) {
            if(currentSum+num>mid){
                count++;
                currentSum=num;
                if(count>m){
                    return false;
                }
            }else {
                currentSum+=num;
            }
        }
        return true;
    }
}