跳转至

二分搜索

字数 745 个   代码 585 行   图片 1 张   阅读时间 10 分钟   访问量

一句话解释

每次比较中间元素，若未命中则排除一半无效区间，逐步缩小搜索范围。

一、算法图解

1.1 Manim 动画演示

binary-search

Manim 动画演示源代码

1.2 Mermaid 流程图示意

graph TD

二、算法性质

2.1 时间复杂度

时间复杂度为 \(O(\log_{2} n)\)。

2.2 空间复杂度

空间复杂度为 \(O(1)\)。

2.3 其它性质

三、算法实现

3.1 多语言代码

下面提供了多种语言的版本，仅供参考。部分编程语言下方提供了可视化代码，但加载可能稍慢，请耐心等待。

适用条件：序列升序且无重复元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) >> 1
        if arr[mid] < target:
            left = mid + 1
        elif arr[mid] > target:
            right = mid - 1
        else:
            return mid
    return -1
可视化代码 🔍全屏查看 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int binarySearch(const std::vector<int> &arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] < target) {
            left = mid + 1;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}
可视化代码 🔍全屏查看 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int binarySearch(ArrayList<Integer> arr, Integer target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr.get(mid) < target) {
            left = mid + 1;
        } else if (arr.get(mid) > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}
可视化代码 🔍全屏查看 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const mid = (left + right) >> 1;;
        if (arr[mid] < target) {
            left = mid + 1;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}
可视化代码 🔍全屏查看 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] < target) {
            left = mid + 1;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}
可视化代码 🔍全屏查看 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int BinarySearch(List<int> arr, int target) {
    int left = 0, right = arr.Count - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] < target) {
            left = mid + 1;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

非常抱歉！pythontutor 暂时还不支持 C# 的可视化！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := (left + right) >> 1
        if arr[mid] < target {
            left = mid + 1
        } else if arr[mid] > target {
            right = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

非常抱歉！pythontutor 暂时还不支持 Go 的可视化！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
fn binary_search(arr: &Vec<i32>, target: i32) -> i32 {
    let (mut left, mut right) = (0, arr.len() as i32 - 1);
    while left <= right {
        let mid = (left + right) >> 1;
        if arr[mid as usize] < target {
            left = mid + 1;
        } else if arr[mid as usize] > target {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

非常抱歉！pythontutor 暂时还不支持 Rust 的可视化！

3.2 自我测试

下面是一个 Python 交互式环境，你可以在其中编写自己的代码进行一些测试。初次启动需要较长时间，请耐心等待！

交互式编程 🚀启动环境 ⚡运行

%reset -f

def binary_search(arr: list[int], target: int) -> int:
    pass

if __name__ == "__main__":
    arr: list[int] = [0, 1, 2, 3, 4, 5, 6, 7]
    print(binary_search(arr, 4))

四、算法扩展

4.1 搜索左右边界

上面给出的代码只能获取不包含重复元素的顺序序列 arr 中目标值 target 的索引，并不能处理包含重复元素的情况。但如果变换思路，获取顺序序列中满足某个条件的左边界或者右边界，就很容易根据问题得到想要的结果。

  • 左边界：满足 >= target 的最左元素
  • 右边界：满足 <= target 的最右元素

对于包含重复元素的升序序列，左右边界可以准确地描述我们需要的内容。

适用条件：序列升序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def binary_search_left(arr: list[int], target: int) -> int:
    left, right, index = 0, len(arr) - 1, -1
    while left <= right:
        mid = (left + right) >> 1
        if arr[mid] >= target:
            index = mid
            right = mid - 1
        else:
            left = mid + 1
    return index


def binary_search_right(arr: list[int], target: int) -> int:
    left, right, index = 0, len(arr) - 1, -1
    while left <= right:
        mid = (left + right) >> 1
        if arr[mid] <= target:
            index = mid
            left = mid + 1
        else:
            right = mid - 1
    return index

 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
int binarySearchLeft(const std::vector<int> &arr, int target) {
    int left = 0, right = arr.size() - 1, index = -1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] >= target) {
            index = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return index;
}

int binarySearchRight(const std::vector<int> &arr, int target) {
    int left = 0, right = arr.size() - 1, index = -1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] <= target) {
            index = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return index;
}

 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
int binarySearchLeft(ArrayList<Integer> arr, Integer target) {
    int left = 0, right = arr.size() - 1, index = -1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr.get(mid) >= target) {
            index = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return index;
}

int binarySearchRight(ArrayList<Integer> arr, Integer target) {
    int left = 0, right = arr.size() - 1, index = -1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr.get(mid) <= target) {
            index = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return index;
}

 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
function binarySearchLeft(arr, target) {
    let left = 0, right = arr.length - 1, index = -1;
    while (left <= right) {
        const mid = (left + right) >> 1;
        if (arr[mid] >= target) {
            index = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return index;
}

function binarySearchRight(arr, target) {
    let left = 0, right = arr.length - 1, index = -1;
    while (left <= right) {
        const mid = (left + right) >> 1;
        if (arr[mid] <= target) {
            index = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return index;
}

 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
int binarySearchLeft(int arr[], int n, int target) {
    int left = 0, right = n - 1, index = -1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] >= target) {
            index = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return index;
}

int binarySearchRight(int arr[], int n, int target) {
    int left = 0, right = n - 1, index = -1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] <= target) {
            index = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return index;
}

 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
int BinarySearchLeft(List<int> arr, int target) {
    int left = 0, right = arr.Count - 1, index = -1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] >= target) {
            index = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return index;
}

int BinarySearchRight(List<int> arr, int target) {
    int left = 0, right = arr.Count - 1, index = -1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] <= target) {
            index = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return index;
}

 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
func binarySearchLeft(arr []int, target int) int {
    left, right, index := 0, len(arr)-1, -1
    for left <= right {
        mid := (left + right) >> 1
        if arr[mid] >= target {
            index = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return index
}

func binarySearchRight(arr []int, target int) int {
    left, right, index := 0, len(arr)-1, -1
    for left <= right {
        mid := (left + right) >> 1
        if arr[mid] <= target {
            index = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return index
}

 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
fn binary_search_left(arr: &Vec<i32>, target: i32) -> i32 {
    let (mut left, mut right, mut index) = (0, arr.len() as i32 - 1, -1);
    while left <= right {
        let mid = (left + right) >> 1;
        if arr[mid as usize] >= target {
            index = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return index;
}

fn binary_search_right(arr: &Vec<i32>, target: i32) -> i32 {
    let (mut left, mut right, mut index) = (0, arr.len() as i32 - 1, -1);
    while left <= right {
        let mid = (left + right) >> 1;
        if arr[mid as usize] <= target {
            index = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return index;
}

4.2 搜索峰谷值

二分搜索除了可以搜索左右边界之外，还可以搜索序列中的峰值和谷值。

  • 峰值：严格大于其左右相邻元素的值
  • 谷值：严格小于其左右相邻元素的值

对于序列的边界值，一般只考虑其存在元素的那一边，但有时也认为它们既不是峰值，也不是谷值，依具体进行分析。此处仅按照前者，考虑其存在元素的一边。

适用条件：序列中相邻元素的值不相等

 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
def binary_search_peak(arr: list[int]) -> int:
    left, right = 1, len(arr) - 2
    index = 0 if arr[0] > arr[-1] else len(arr) - 1
    while left <= right:
        mid = (left + right) >> 1
        if arr[mid - 1] > arr[mid]:
            right = mid - 1
        elif arr[mid + 1] > arr[mid]:
            left = mid + 1
        else:
            index = mid
            break
    return index


def binary_search_valley(arr: list[int]) -> int:
    left, right = 1, len(arr) - 2
    index = 0 if arr[0] < arr[-1] else len(arr) - 1
    while left <= right:
        mid = (left + right) >> 1
        if arr[mid - 1] < arr[mid]:
            right = mid - 1
        elif arr[mid + 1] < arr[mid]:
            left = mid + 1
        else:
            index = mid
            break
    return index

 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
int binarySearchPeak(const std::vector<int> &arr) {
    int left = 1, right = arr.size() - 2;
    int index = arr.front() > arr.back() ? 0 : arr.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid - 1] > arr[mid]) {
            right = mid - 1;
        } else if (arr[mid + 1] > arr[mid]) {
            left = mid + 1;
        } else {
            index = mid;
            break;
        }
    }
    return index;
}

int binarySearchValley(const std::vector<int> &arr) {
    int left = 1, right = arr.size() - 2;
    int index = arr.front() < arr.back() ? 0 : arr.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid - 1] < arr[mid]) {
            right = mid - 1;
        } else if (arr[mid + 1] < arr[mid]) {
            left = mid + 1;
        } else {
            index = mid;
            break;
        }
    }
    return index;
}

 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
int binarySearchPeak(ArrayList<Integer> arr) {
    int left = 1, right = arr.size() - 2;
    int index = arr.get(0) > arr.get(arr.size() - 1) ? 0 : arr.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr.get(mid - 1) > arr.get(mid)) {
            right = mid - 1;
        } else if (arr.get(mid + 1) > arr.get(mid)) {
            left = mid + 1;
        } else {
            index = mid;
            break;
        }
    }
    return index;
}

int binarySearchValley(ArrayList<Integer> arr) {
    int left = 1, right = arr.size() - 2;
    int index = arr.get(0) < arr.get(arr.size() - 1) ? 0 : arr.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr.get(mid - 1) < arr.get(mid)) {
            right = mid - 1;
        } else if (arr.get(mid + 1) < arr.get(mid)) {
            left = mid + 1;
        } else {
            index = mid;
            break;
        }
    }
    return index;
}

 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
function binarySearchPeak(arr) {
    let left = 1, right = arr.length - 2;
    let index = arr[0] > arr[arr.length - 1] ? 0 : arr.length - 1;
    while (left <= right) {
        const mid = (left + right) >> 1;
        if (arr[mid - 1] > arr[mid]) {
            right = mid - 1;
        } else if (arr[mid + 1] > arr[mid]) {
            left = mid + 1;
        } else {
            index = mid;
            break;
        }
    }
    return index;
}

function binarySearchValley(arr) {
    let left = 1, right = arr.length - 2;
    let index = arr[0] < arr[arr.length - 1] ? 0 : arr.length - 1;
    while (left <= right) {
        const mid = (left + right) >> 1;
        if (arr[mid - 1] < arr[mid]) {
            right = mid - 1;
        } else if (arr[mid + 1] < arr[mid]) {
            left = mid + 1;
        } else {
            index = mid;
            break;
        }
    }
    return index;
}

 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
int binarySearchPeak(int arr[], int n) {
    int left = 1, right = n - 2;
    int index = arr[0] > arr[n - 1] ? 0 : n - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid - 1] > arr[mid]) {
            right = mid - 1;
        } else if (arr[mid + 1] > arr[mid]) {
            left = mid + 1;
        } else {
            index = mid;
            break;
        }
    }
    return index;
}

int binarySearchValley(int arr[], int n) {
    int left = 1, right = n - 2;
    int index = arr[0] < arr[n - 1] ? 0 : n - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid - 1] < arr[mid]) {
            right = mid - 1;
        } else if (arr[mid + 1] < arr[mid]) {
            left = mid + 1;
        } else {
            index = mid;
            break;
        }
    }
    return index;
}

 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
int BinarySearchPeak(List<int> arr) {
    int left = 1, right = arr.Count - 2;
    int index = arr.First() > arr.Last() ? 0 : arr.Count - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid - 1] > arr[mid]) {
            right = mid - 1;
        } else if (arr[mid + 1] > arr[mid]) {
            left = mid + 1;
        } else {
            index = mid;
            break;
        }
    }
    return index;
}

int BinarySearchValley(List<int> arr) {
    int left = 1, right = arr.Count - 2;
    int index = arr.First() < arr.Last() ? 0 : arr.Count - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid - 1] < arr[mid]) {
            right = mid - 1;
        } else if (arr[mid + 1] < arr[mid]) {
            left = mid + 1;
        } else {
            index = mid;
            break;
        }
    }
    return index;
}

 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
func BinarySearchPeak(arr []int) int {
    left, right := 1, len(arr)-2
    index := len(arr) - 1
    if arr[0] > arr[len(arr)-1] {
        index = 0
    }
    for left <= right {
        mid := (left + right) >> 1
        if arr[mid-1] > arr[mid] {
            right = mid - 1
        } else if arr[mid+1] > arr[mid] {
            left = mid + 1
        } else {
            index = mid
            break
        }
    }
    return index
}

func BinarySearchValley(arr []int) int {
    left, right := 1, len(arr)-2
    index := len(arr) - 1
    if arr[0] < arr[len(arr)-1] {
        index = 0
    }
    for left <= right {
        mid := (left + right) >> 1
        if arr[mid-1] < arr[mid] {
            right = mid - 1
        } else if arr[mid+1] < arr[mid] {
            left = mid + 1
        } else {
            index = mid
            break
        }
    }
    return index
}

 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
fn binary_search_peak(arr: &Vec<i32>) -> i32 {
    let (mut left, mut right) = (1, arr.len() as i32 - 2);
    let mut index = if arr.first() > arr.last() { 0 } else { arr.len() as i32 - 1 };
    while left <= right {
        let mid = (left + right) >> 1;
        if arr[mid as usize - 1] > arr[mid as usize] {
            right = mid - 1;
        } else if arr[mid as usize + 1] > arr[mid as usize] {
            left = mid + 1;
        } else {
            index = mid;
            break;
        }
    }
    return index;
}

fn binary_search_valley(arr: &Vec<i32>) -> i32 {
    let (mut left, mut right) = (1, arr.len() as i32 - 2);
    let mut index = if arr.first() < arr.last() { 0 } else { arr.len() as i32 - 1 };
    while left <= right {
        let mid = (left + right) >> 1;
        if arr[mid as usize - 1] < arr[mid as usize] {
            right = mid - 1;
        } else if arr[mid as usize + 1] < arr[mid as usize] {
            left = mid + 1;
        } else {
            index = mid;
            break;
        }
    }
    return index;
}

  1. 10.1   二分查找 - Hello 算法 ↩

  2. 二分 - OI Wiki ↩

  3. 算法讲解006【入门】二分搜索_哔哩哔哩_bilibili ↩

  4. 162. 寻找峰值 ↩

  5. 1901. 寻找峰值 II ↩

  6. 2951. 找出峰值 ↩