关于二分查找法

发表于 | 分类于

概述

二分查找法是一种很常用的查找算法，利用二分查找法可以在有序数组中以对数级别的复杂度下完成查找。关于二分查找法，有很多变种，其中的区别很微妙。最重要的是，无论有多少种变种的二分查找，能写对一种就行。

二分查找的基本思路：将查找的键和数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。

算法

对于升序序列a，寻找关键字key，序列a中元素的个数为n

求最小的i，使得a[i] = key，若不存在，则返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binary_search(int a[], int n, int key) {
        int mid, left = 0, right = n - 1;
        while (left < right) {
            mid = left + ((right - left) >> 1);
            if (a[mid] < key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (a[right] == key) {
            return right;
        }
        return -1;
    }

求最小的i，使得a[i] > key，若不存在，则返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binary_search(int a[], int n, int key) {
        int mid, left = 0, right = n - 1;
        while (left < right) {
            mid = left + ((right - left) >> 1);
            if (a[mid] <= key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (a[right] > key) {
            return right;
        }
        return -1;
    }

求最大的i，使得a[i] = key，若不存在，则返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binary_search(int a[], int n, int key) {
    int mid, left = 0, right = n - 1;
    while (left < right) {
        mid = left + ((right + 1 - left) >> 1);
        if (a[mid] <= key) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    if (a[left] == key) {
        return left;
    }
    return -1;
}

求最大的i，使得a[i] < key，若不存在，则返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binary_search(int a[], int n, int key) {
    int mid, left = 0, right = n - 1;
    while (left < right) {
        mid = left + ((right + 1 - left) >> 1);
        if (a[mid] < key) {
            left = mid ;
        } else {
            right = mid - 1;
        }
    }
    if (a[left] < key) {
        return left;
    }
    return -1;
}

写对一种就行!

最后介绍一个我个人用的比较多的版本，二分查找法如果查找失败就返回应该插入的位置的索引,这也是Leetcode 35题的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int searchInsert(int[] nums, int target) {
    int low = 0;
    int high = nums.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] < target) {
            low = mid + 1;
        }
        if (nums[mid] >= target) {
            high = mid - 1;
        }
    }
    return low;
}

练习

在Leetcode上有一些使用到二分查找的题目，我们可以来练练手。

0%