二分法

2026-04-01 算法

二分法

1. 题目描述

提示
题目链接：https://leetcode.cn/problems/binary-search/description/

2. 解题思路

核心总结

核心思想：通过中间值缩小查询范围。
写法对比：
1. 左闭右闭 [left, right]：while(left <= right)，right = middle - 1。因为 left == right 是有意义的。
2. 左闭右开 [left, right)：while(left < right)，right = middle。此时 left == right 在区间里没有意义。

💡 易错点

二分法的判断条件是左右标志的大小，每次查询后计算中间值，注意区间定义的开闭一致性。

3. 代码实现

class Solution {

    public int search(int[] nums, int target) {

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

        while(left <= right){

            int mid = (left + right) / 2;

            if(nums[mid] > target){

                right = mid - 1;

            }else if(nums[mid] < target){

                left = mid + 1;

            }else

                return mid;

        }

        return -1;

    }

}

4. 复杂度分析

时间复杂度：$O(n)$
空间复杂度：$O(1)$

5. 总结与反思

本文已被观测了次