引言

二分查找是最基础也是最重要的算法之一，时间复杂度O(log n)。本文系统讲解二分查找的原理和应用。

一、基础二分查找

1.1 基本模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int binarySearch(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;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

1.2 搜索插入位置（LeetCode 35）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int searchInsert(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 {
            right = mid - 1;
        }
    }
    
    return left;
}

二、二分查找变种

2.1 搜索旋转排序数组（LeetCode 33）

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
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[left] <= nums[mid]) {
            // 左半部分有序
            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;
}

2.2 寻找峰值（LeetCode 162）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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. 基础模板：left <= right
  2. 边界处理：防止整数溢出
  3. 变种问题：旋转数组、峰值查找

参考资料