二分查找

发表于 | 分类于 | 阅读次数:
字数统计: 1.9k | 阅读时长 ≈ 8

查找不外乎顺序查找、二分查找、哈希表查找和二叉排序树查找。 二分查找是一个基础的算法，也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。

二分查找

如果题目中要求在排序的数组（或者部分排序的数组）中查找一个数字或者统计某个数字出现的次数，那么都可以尝试用二分查找算法。
哈希表和二叉树炸找的重点在于考查对应的数据结构而不是算法。

极客时间-二分查找

二分查找代码

每次移动left和right指针的时候，需要在mid的基础上+1或者-1， 防止出现死循环， 程序也就能够正确的运行。

注意：代码中的判断条件必须是while (left <= right)，否则的话判断条件不完整，比如：array[3] = {1, 3, 5};待查找的键为5，此时在(low < high)条件下就会找不到，因为low和high相等时，指向元素5，但是此时条件不成立，没有进入while()中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @description: 二分查找
 * @author: rhsphere
 * @since: 2019-11-04 22:06 by jdk 1.8
 */
public class BinarySearch {


    public int search1(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

二分查找的变种

关于二分查找，如果条件稍微变换一下，比如：数组之中的数据可能可以重复，要求返回匹配的数据的最小（或最大）的下标；更近一步， 需要找出数组中第一个大于key的元素（也就是最小的大于key的元素的）下标，等等。 这些，虽然只有一点点的变化，实现的时候确实要更加的细心。

二分查找的变种和二分查找原理一样，主要就是变换判断条件（也就是边界条件），如果想直接看如何记忆这些变种的窍门，请直接翻到本文最后。下面来看几种二分查找变种的代码：

查找第一个与key相等的元素

查找第一个相等的元素，也就是说等于查找key值的元素有好多个，返回这些元素最左边的元素下标。

当执行到right == left == mid后，此时会执行，if的 if (arr[mid] >= key) 分支，于是right = left - 1，于是跳出while循环，所以最后时 left是 arr[key]最有左边的值，而right正好卡在left左边。

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
/**
 * @description: 使用二分查找第一个给定值的元素
 * @author: rhsphere
 * @since: 2019-11-04 22:21 by jdk 1.8
 */
public class BinarySearchFirst {

    public int binarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] >= key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        if (low < arr.length && arr[low] == key) {
            return low;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @description:
 * @author: rhsphere
 * @since: 2019-11-04 22:24 by jdk 1.8
 */
public class BinarySearchFirstTest {

    private BinarySearchFirst binaryFirst = new BinarySearchFirst();

    @Test
    public void binarySearch() {
//        int[] data = new int[] {1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9, 10};
        int[] data = new int[] {0,0,0,0,0,0,0,1,1,1,1,1,1,1};

        int index = binaryFirst.binarySearch(data, 1);

        System.out.println("查找的索引下标为:" + index);
    }
}

查找最后一个与key相等的元素

查找最后一个相等的元素，也就是说等于查找key值的元素有好多个，返回这些元素最右边的元素下标。

根据上面的分析，left == right == mid 的时候，left = mid + 1，于是left卡在了right右边，所以应该返回right值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @description: 二分查找最后一个
 * @author: rhsphere
 * @since: 2019-11-04 22:44 by jdk 1.8
 */
public class BinarySearchLast {

    public int binarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] <= key) {
                low = mid +1;
            } else {
                high = mid - 1;
            }
        }
        if (high >= 0 && arr[high] == key)
            return high;
        return -1;
    }
}

查找最后一个等于或小于key的元素

查找最后一个等于或小于key的元素，也就是说等于查找key值的元素有好多个，返回这些元素最右边的元素下标；如果没有等于key值的元素，则返回小于key的最右边元素下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @description:
 * @author: rhsphere
 * @since: 2019-11-04 22:51 by jdk 1.8
 */
public class BinarySearchLastEqualSmaller {

    public int findLastEqualSmaller(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return high;
    }
}

查找第一个等于或者大于key的元素

查找第一个等于或者大于key的元素，也就是说等于查找key值的元素有好多个，返回这些元素最左边的元素下标；如果没有等于key值的元素，则返回大于key的最左边元素下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @description: 查找第一个等于或者大于key的元素
 * @author: rhsphere
 * @since: 2019-11-04 22:57 by jdk 1.8
 */
public class BinarySearchFirstEqualLarger {

    public int findFirstEqualLarger(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] >= key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}

查找最后一个小于key的元素

查找最后一个小于key的元素，也就是说返回小于key的最右边元素下标。

返回最后一个小于key的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
public static int findLastSmaller(int[] arr, int key) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) >> 1;
        if (arr[mid] >= key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return right;
}

查找第一个大于key的元素

查找第一个等于key的元素，也就是说返回大于key的最左边元素下标。

查找第一个大于key的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
public static int findFirstLarger(int[] arr, int key) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) >> 1;
        if (arr[mid] > key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

二分查找变种总结

二分查找核心
1
2
3
4
5
6
7
8
9
while (left <= right) {
    int mid = (left + right) / 2;
    if (arr[mid] ? key) {
        //...right = mid - 1;
    } else {
        //...left = mid + 1;
    }
}
return xxx;

首先判断出返回left，还是right

因为最后跳出 while (left <= right) 循环条件是 right < left 且 right = left - 1。最后right和left一定卡在“边界值”的左右两边，如果比较值是key，查找小于等于（或是小于）key的元素，则边界值就是等于key的所有元素的最左边那个，其实应该返回left。

判断出比较符号

二分查找判断符号
1
2
3
4
5
6
int mid = (left + right) / 2;
if (arr[mid] ? key) {
    //...right = mid - 1;
} else {
    //...left = mid + 1;
}

也就是这里的if (array[mid] ? key) 中的判断符号，结合步骤1和给出的条件，如果是查找小于等于key的元素，则知道应该使用判断符号>=，因为是要返回left，所以如果array[mid]等于或者大于key，就应该使用>=，以下是完整代码

查找小于等于key的元素
1
2
3
4
5
6
int mid = (left + right) / 2;
if (arr[mid] >= key) {
    right = mid - 1;
} else {
    left = mid + 1;
}
0%