Neko's Blog
算法

二分搜索法

2026-05-27 #算法

letcode 704

在一个数组里，找一个target, 判断target 是否在数组中，如果在返回对应的数组下标,没找到返回-1

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.

给定一个按升序排列的整数数组 nums 和一个整数 target，编写一个函数在 nums 中搜索 target。如果 target 存在，则返回其下标；否则返回 -1。
你必须编写一个时间复杂度为 O(log n) 的算法。

以下是二分查找法的核心算法思想：

🔍 二分查找法（Binary Search）核心思想

  1. 基本前提
  • 数组必须是有序的（升序或降序）
  • 通过不断缩小搜索范围来快速定位目标
  1. 核心思路
  • 每次取中间元素与目标值比较
  • 如果相等 → 找到目标，返回下标
  • 如果中间值 < 目标 → 目标在右半部分，舍弃左半部分
  • 如果中间值 > 目标 → 目标在左半部分，舍弃右半部分
  • 重复上述过程，直到找到目标或搜索范围为空
  1. 三个关键变量
  • left：搜索范围的左边界
  • right：搜索范围的右边界
  • mid：中间位置，mid = left + (right - left) / 2
  1. 两种区间写法

写法一：左闭右闭 [left, right]
left = 0, right = nums.length - 1
while (left <= right):
mid = left + (right - left) / 2
if nums[mid] == target → return mid
if nums[mid] < target → left = mid + 1
if nums[mid] > target → right = mid - 1

写法二：左闭右开 [left, right)
left = 0, right = nums.length
while (left < right):
mid = left + (right - left) / 2
if nums[mid] == target → return mid
if nums[mid] < target → left = mid + 1
if nums[mid] > target → right = mid

  1. 为什么 mid 不用 (left+right)/2？
  • 防止整数溢出
  • left + (right - left) / 2 更安全
  1. 时间 & 空间复杂度
  • 时间：O(log n) — 每次砍掉一半
  • 空间：O(1) — 只用常数额外空间
  1. 易错点
  • 循环条件：<= 还是 <？取决于区间定义
  • 边界更新：mid+1/mid-1 还是 mid？取决于区间定义
  • 两种写法不能混用，选定一种就贯彻到底
  1. 适用场景
  • 有序数组查找
  • 查找第一个/最后一个满足条件的元素
  • 旋转排序数组查找
  • 答案具有单调性的问题（二分答案）

💡 一句话总结：二分查找的本质是每次排除一半不可能的选项，把 O(n) 的暴力搜索优化到 O(log n)。

区间定义[left,right]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int search(int[] nums, int target) {
        // 定义当前区间 [left,right]
        int left = 0;
        int right = nums.length - 1;
        int middle = 0;

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

区间定义[left,right)，这里的有边界取数组lenth 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int search(int[] nums, int target) {
        // 定义当前区间 [left,right)
        int left = 0;
        int right = nums.length;
        int middle = 0 ;

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

leetcode 34

Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.
给定一个按非递减顺序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

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

你必须编写一个时间复杂度为 O(log n) 的算法。
我的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class BinarySearchFindPosition {
    public int[] searchRange(int[] nums, int target) {
        int[] array = new int[nums.length];
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                array[count] = i;
                count++;
            } else continue;
        }
        if (array.length == 0 || count== 0) {
            return new int[]{-1, -1};
        }
        return new int[]{array[0], array[count-1]};
    }
}

核心思想总结：

这是 LeetCode 第 34 题「在排序数组中查找元素的第一个和最后一个位置」，核心是 二分查找的两次变体：

  1. 两次二分：

    • 第一次：找到 target 的 左边界（第一次出现的位置）
    • 第二次：找到 target 的 右边界（最后一次出现的位置）

  2. 左边界二分：

    • 当 nums[mid] >= target 时，向左收缩（right = mid - 1）
    • 记录最后满足 nums[mid] == target 的位置

  3. 右边界二分：

    • 当 nums[mid] <= target 时，向右收缩（left = mid + 1）
    • 记录最后满足 nums[mid] == target 的位置

  4. 特殊情况：

    • 如果左边界不存在（-1），直接返回 [-1, -1]
    • 空数组自动处理

时间复杂度：两次 O(log n) → 总计 O(log n)
空间复杂度：O(1)

java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class BinarySearchFindPosition {
    public int[] searchRange(int[] nums, int target) {
        int left = findLeft(nums, target);
        if (left == -1) {
            return new int[]{-1, -1};
        }
        int right = findRight(nums, target);
        return new int[]{left, right};
    }

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

        }
        return ans;
    }

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

        }
        return ans;
    }


    public static void main(String[] args) {
        BinarySearchFindPosition sol = new BinarySearchFindPosition();
        int[] nums1 = {5, 7, 7, 8, 8, 10};
        int[] res1 = sol.searchRange(nums1, 8);
        System.out.println(java.util.Arrays.toString(res1)); // [3,4]

        int[] nums2 = {5, 7, 7, 8, 8, 10};
        int[] res2 = sol.searchRange(nums2, 6);
        System.out.println(java.util.Arrays.toString(res2)); // [-1,-1]

        int[] nums3 = {};
        int[] res3 = sol.searchRange(nums3, 0);
        System.out.println(java.util.Arrays.toString(res3)); // [-1,-1]
    }
}

leetcode 35

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

给定一个由 不同整数 组成的 已排序 数组和一个目标值 target，如果在数组中找到目标值，则返回其索引；否则，返回目标值应该被 按顺序插入 的位置（即保持数组有序的索引）。

你必须实现一个时间复杂度为 O(log n) 的算法
我的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid = 0;

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

核心思想（算法思路）

这是一道典型的 二分查找 变体 — — “搜索插入位置”。
数组是 严格递增（distinct + 已排序），因此可以用二分法在 O(log n) 时间内定位目标。

  1. 维护两个指针 left、right，分别表示搜索区间的左右边界（初始为 [0, n‑1]）。
  2. 每次取中间位置 mid = left + (right‑left)/2。
    • 如果 nums[mid] == target → 直接返回 mid（找到目标）。
    • 如果 nums[mid] < target → 目标一定在 mid 右侧，令 left = mid + 1。
    • 如果 nums[mid] > target → 目标一定在 mid 左侧（或应该插入的位置就在 mid 处），令 right = mid - 1。
  3. 循环结束时，left 指向第一个 大于 target 的位置，也正是目标应该被插入的索引（若 target 存在的话，之前已经返回了）。
  4. 返回 left 即可。

时间复杂度：每轮排除一半 → O(log n)
空间复杂度：只用了几个整型变量 → O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {
    /**
     * LeetCode 35: Search Insert Position
     * 给定一个无重复元素的升序数组，返回目标值的索引；
     * 若不存在，则返回目标值应该被插入的位置（以保持数组有序）。
     * 时间复杂度 O(log n)，空间复杂度 O(1)。
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int 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;             // 目标在右半部
            } else {
                right = mid - 1;            // 目标在左半部（或应插入于 mid）
            }
        }
        // 循环结束，left 是第一个大于 target 的位置，也是插入点
        return left;
    }

    // 简单的 main 方法用于演示
    public static void main(String[] args) {
        Solution sol = new Solution();

        int[] nums1 = {1, 3, 5, 6};
        System.out.println(sol.searchInsert(nums1, 5)); // 2
        System.out.println(sol.searchInsert(nums1, 2)); // 1
        System.out.println(sol.searchInsert(nums1, 7)); // 4

        int[] nums2 = {1, 3, 5, 6};
        System.out.println(sol.searchInsert(nums2, 0)); // 0
        System.out.println(sol.searchInsert(nums2, 2)); // 1
    }
}
评论
分享

相关文章

查看更多
有序数组的平方
有序数组的平方 2026-06-06
移除元素
移除元素 2026-06-06
算法学习记录
算法学习记录 2026-04-23