二分查找

# 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） (opens new window)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{left_bound(nums,target),right_bound(nums,target)};
    }
    //常规
    int binary_search(int[] nums,int target){
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                //直接返回
                right = mid;
            }
        }
        //直接返回
        return -1;
    }
    //搜索左边界
    int left_bound(int[] nums,int target){
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                //别返回，锁定左侧边界
                right = mid - 1;
            }
        }
        //判断 target 是否存在于nums中
        if (left < 0 || left >= nums.length) {
            return -1;
        }
        //判断一下nums[left]是不是target
        return nums[left] == target ? left : -1;
    }
    //搜索右边界
    int right_bound(int[] nums,int target){
        int left = 0,right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target){
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                //别返回，锁定右侧边界
                left = mid + 1;
            }
        }
        //由于while的结束条件是right == left - 1,且现在在求右边界
        //所以用right代替 left - 1更好记住
        if (right < 0 || right >= nums.length) {
            return -1;
        }     
        return nums[right] == target ? right : -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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

# 704. 二分查找 - 力扣（LeetCode） (opens new window)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 162. 寻找峰值 - 力扣（LeetCode） (opens new window)

left < right 保证循环结束时 left == right，此时仅剩一个元素，直接返回该位置即为峰值索引

若用 left <= right：当 left == right 时循环仍会执行，但此时 mid = left，后续比较 nums[mid] 与 nums[mid + 1] 可能导致 数组越界（因 mid + 1 可能超出边界）

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 35. 搜索插入位置 - 力扣（LeetCode） (opens new window)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 33. 搜索旋转排序数组 - 力扣（LeetCode） (opens new window)

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] >= nums[left]){
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -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

编辑

上次更新: 2025/07/16, 10:21:39

← 位运算递归→