【LeetCode：704 二分查找】快速学会二分查找,以及相关习题

超级苦力怕

发布于 2025-12-24 08:59:35

310

前置知识：无

1. 二分查找：原理、模板与经典题解

一句话：在有序范围内，反复比较中点，每次把搜索区间缩小一半，直至命中或区间为空。

使用前提：二分查找仅适用于 「有序数据」（如升序或降序排列的数组、列表等），这是其能高效缩窄范围的基础。

示例：

在 [1,3,5,9,13,15,23,25] 中查找 15：
- 中点 9 < 15，区间缩到 [13,15,23,25]
- 中点 15 命中，返回 true

基本原理：

确定初始范围：假设数据是升序的，初始搜索范围为整个数据集（用左右指针 left 和 right 标记边界）。
找到中间位置：计算范围中间的索引 mid，并获取对应的值 nums[mid]。
比较与缩窄范围：

若 nums[mid] == target：找到目标，返回 mid（查找成功）。
若 nums[mid] > target：目标在左半部分，缩小右边界（right = mid - 1 或 right = mid，取决于区间定义）。
若 nums[mid] < target：目标在右半部分，扩大左边界（left = mid + 1）。

重复直至范围为空：若 left 超出 right（范围为空），说明目标不存在，返回特定值（如 -1）。

常见种类：二分查找的实现需明确搜索范围的区间定义（影响指针移动和循环条件），常见两种：

左闭右闭 [left, right]：left 和 right 均为有效索引，循环条件 left <= right，移动指针时需跳过 mid（如 right = mid - 1）。
左闭右开 [left, right)：left 有效，right 无效（指向范围外），循环条件 left < right，移动右指针时直接设为 mid（如 right = mid）。

代码示例（判断是否存在）：

	public static boolean exist(int[] arr, int num) {
		if (arr == null || arr.length == 0) {
			return false;
		}
		int left = 0, right = arr.length - 1, m = 0;
		while (left <= right) {
			m = left + ((right - left) >> 1);
			if (arr[m] == num) {
				return true;
			} else if (arr[m] > num) {
				right = m - 1;
			} else {
				left = m + 1;
			}
		}
		return false;
	}

提示：m = l + ((r - l) >> 1) 可避免直接 l + r 可能的整型溢出。
提示：二分不只用于“有序数组”，也常用于“单峰/单调性”结构（如峰值问题）。

2. 统一模板速查

左闭右闭 [left, right]

不变量：区间始终包含所有候选；循环条件 left <= right。

// lower_bound: 第一个 >= target 的位置（若不存在，返回插入点）
int lowerBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1, ans = nums.length;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= target) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

// upper_bound: 第一个 > target 的位置；最后一个 <= target 为 upper_bound - 1
int upperBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1, ans = nums.length;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] > target) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

左闭右开 [left, right)

不变量：区间始终为有效候选；循环条件 left < right。

int lowerBoundHalfOpen(int[] nums, int target) {
    int left = 0, right = nums.length; // 右端为开区间
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

小贴士：

计算 mid 用 left + ((right - left) >> 1) 防溢出。
选择哪种区间定义，关键是保持“循环条件、指针移动、不变量”三者一致。

3. LeetCode 相关习题讲解

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]之间

思路

这道题目给出了两个有效的条件，一个是有序数组，一个是数组中无重复元素，这些都是使用二分法的前提条件，因此使用二分法。

二分法对于区间的定义一般分为两种，左闭右闭[left,right]，左闭右开[left,right]，基于两种进行书写。

写法一：左闭右闭 [left,right]

因为定义target在[left,right]区间，因此有以下两点

1.while(left <= right)需要使用 <=，因为left==right有意义拓：当left == right时，区间退化为 [x, x]（x 是同一个索引），这个区间包含且仅包含一个元素（nums[x]） 2.if(nums[m] > target)中right = m-1，因为当前的nums[m] ！= target,因此接下来查找左边（以升序为例），下一次查找的区间最右侧为m-1;

写法：

class Solution {
    public int search(int[] nums, int target) {
        if(nums ==null || nums.length == 0 ){
            return -1;
        }
        int left=0,right=nums.length-1,m=0;
        while(left<=right){
            m=left+(right-left)/2;
            if(nums[m]==target){
                return m;
            }else if(nums[m] < target){
                left=m+1;  // target 在右区间，在[m + 1, right)中
            }else{
                right=m-1; // target 在左区间，在[left, m-1)中
            }
        }
        return -1;
    }
}

写法二：左闭右开 [left,right)

因为定义target在[left,right)区间，因此有以下两点

1.while(left < right)，这里使用 <，因为left==right在区间[left,right）无意义拓：此处的right指向区间外无效元素,因此当left == right时，区间退化为[x,x)，右端点x不被包含，因此这个区间不包含任何元素。 2.if(nums[m] > target)中right = m，因为当前的nums[m] ！= target,因此接下来查找左边（以升序为例），下一个查询区间不回去比较nums[m]；

写法：

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0, right = nums.length, m = 0;
        while (left < right) {
            m = left + (right - left) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                left = m + 1;  // target 在右区间，在[m + 1, right)中
            } else {
                right = m;  // target 在左区间，在[left, m)中
            }
        }
        return -1;
    }
}

162：峰值元素（中等）

题目简介

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

提示：

1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1 对于所有有效的 i 都有 nums[i] != nums[i + 1]

思路

使用二分查找找到峰值即可

峰值问题：给定数组，找一个下标 i，使得它比相邻元素都大（arr[i] > arr[i-1] 且 arr[i] > arr[i+1]）。边界元素只需比唯一相邻者大即可。 简单理解：将数组看作函数几个点，函数极值点即为峰值。 解决思路： 1.先处理边界：n==1，或 arr[0]>arr[1]，或 arr[n-1]>arr[n-2]，这些都是峰值位置。 2.在区间 [1, n-2] 二分：若 arr[m] < arr[m-1]，峰在左侧；若 arr[m] < arr[m+1]，峰在右侧；否则 m 就是峰。

代码

class Solution {
    public int findPeakElement(int[] nums) {
        int n= nums.length;
        if(n==1){
            return 0;
        }else if(nums[0]>nums[1]){
            return 0;
        }else if(nums[n-1]>nums[n-2]){
            return n-1;
        }

        int left=1,right=n-2,ans=-1,m=0;

        while(left<=right){
            m=(right+left)/2;
            if(nums[m-1]>nums[m]){
                right=m-1;
            }else if(nums[m]<nums[m+1]){
                left=m+1;
            }else{
                ans=m;
                break;
            }
        }
        return ans;
    }
}

35：搜索插入位置（简单）

题目简介

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为无重复元素的升序排列数组
-10^4 <= target <= 10^4

思路

整体思路和普通的二分查找几乎没有区别，先设定左侧下标 left 和右侧下标 right，再计算中间下标 mid

每次根据 nums[mid] 和 target 之间的大小进行判断，相等则直接返回下标，nums[mid] < target 则 left 右移，nums[mid] > target 则 right 左移
查找结束如果没有相等值则返回 left，该值为插入位置

写法:

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left=0,right=nums.length-1,m=0;
        while(left<=right){
            m=left+(right-left)/2;
            if(target==nums[m]){
                return m;
            }else if(nums[m]<target){
                left=m+1;
            }else{
                right=m-1;
            }
        }
        return left;
    }
}

34：在排序数组中查找元素的第一个和最后一个位置（中等）

题目简介

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9

思路

这里涉及到两个边界，因此使用两次二分分别查找左、右端：

target 不在区间内，直接返回 [-1,-1]
target 在区间内但数组中没有，返回 [-1,-1]
target 在区间内且存在，返回正常区间 [l, r]

以查找左边界为例：当 nums[m] == target 时，记录答案并将 right = m - 1，继续向左收缩；右边界同理。

示例

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

代码

这里主要使用两个方法，res 设为 -1，可直接覆盖“未命中”的场景。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[] { -1, -1 };
        }
        int left = getLeft(nums, target);
        if (left == -1) {
            return new int[] { -1, -1 };
        }
        int right = getRight(nums, target);
        return new int[] { left, right };
    }
    public int getLeft(int[] nums, int target) {
        int left = 0, right = nums.length - 1,res=-1;
        while(left<=right){
            int m=left+(right-left)/2;
            if(nums[m] > target){
                right=m-1;
            }else if(nums[m] < target){
                left=m+1;
            }else{
                right=m-1;
                res=m;
            }
        }
        return res;
    }

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

69：x 的平方根（简单）

题目简介

给你一个非负整数 x ，计算并返回 x 的算术平方根。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 2^31 - 1

思路

这道题有三种情况（取结果为 m）：

m*m == x 或 m*m < x && (m+1)*(m+1) > x，返回 m（如示例 2）。
m*m < x，说明偏小，left = m + 1。
m*m > x，说明偏大，right = m - 1。

写法:

实际就是二分，但需防溢出，可用除法替代乘法比较（如 m <= x / m）。

class Solution {
    public int mySqrt(int x) {
        if (x < 2) {
            return x;
        }
        int left = 1, right = x / 2 + 1, ans = 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid <= x / mid) { // mid*mid <= x
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

367：有效的完全平方数（简单）

题目简介

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

提示：

1 <= num <= 2^31 - 1

思路

第一种解法 这道题实则可以和上道题的思路一样,只是多了一个检测结果是否为整数.

class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 1, right = num;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int q = num / mid;
            if (mid == q && num % mid == 0) {
                return true;
            }
            if (mid < q) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

第二种解法 巧合的是，由于这是一个完全平方数，我们可以通过等差数列来进行求解（平方数是连续奇数之和）。写法:

class Solution {
    public boolean isPerfectSquare(int num) {
        int x = 1;
        while (num > 0) {
            num -= x;
            x += 2;
        }
        return num == 0;
    }
}