【算法】查找类——二分查找算法

二分查找算法算法总结

算法描述

该算法属于查找算法。当需要从有序数组中查找某一元素时，可以使用该算法进行查找。（本文章假设数组是升序排列的数组）

算法思想

每次进行对半查找，获取中间元素值，然后与目标值进行比较。

• 如果目标元素等于中间值，则查找成功，返回中间元素的index。
• 如果目标元素小于中间值，则目标在中间值的左侧，则对中间值的左侧进行对半查找。
• 如果目标元素大于中间值，则目标在中间值的右侧，则对中间值的右侧进行对半查找。

当查找区间没有元素时，返回-1，表示没有找到。

接口定义

/*** 标准二分查找法, 在一个数据找找寻value。** @param array 数组 升序排序* @param value 要找的数* @return 如果数组存在与value值相等的元素时，返回首次对半找到的值的index；否则返回-1*/
public int binarySearch(int[] array, int value) {}

代码实现

闭合区间实现方案

/*** 标准二分查找法, 在一个数据找找寻value。** @param array 数组 升序排序* @param value 要找的数* @return 如果数组存在与value值相等的元素时，返回首次对半找到的值的index；否则返回-1*/
public static int binarySearch(int[] array, int value) {int start = 0, end = array.length - 1;  // [start, end] 区间，start和end都能取得while (start <= end) {int mid = (start + end) >>> 1;if (array[mid] < value) {start = mid + 1;} else if (value < array[mid]) {end = mid - 1;} else {return mid;}}return -1;
}

半闭合区间实现

/*** 标准二分查找法, 在一个数据找找寻value。** @param array 数组 升序排序* @param value 要找的数* @return 如果数组存在与value值相等的元素时，返回首次对半找到的值的index；否则返回-1*/
public static int binarySearchEndOpen(int[] array, int value) {int start = 0, end = array.length;  // [start, end) 比区间，end不能去到, end指向非查找目标while (start < end) {int mid = (start + end) >>> 1;if (array[mid] < value) {start = mid + 1;} else if (value < array[mid]) {end = mid;} else {return mid;}}return -1;
}

两个方案总结

如果数据不存在相同元素时，该数组返回值时是相同的。

如果数组存在相同元素时，查找相同元素时，返回的结果会存在不一致的现象。

例子：在同一数组中查找89，一个结果为6，一个结果为7

        /***  相同数查找*  1, 32, 32, 56, 78, 89, 89, 89, 122*  0	1	2	3	4	5	6	7	8*/int[] arrayExistSameValue = {1, 32, 32, 56, 78, 89, 89, 89, 122};Assert.assertEquals(6, BinarySearch.binarySearch(arrayExistSameValue, 89));Assert.assertEquals(7, BinarySearch.binarySearchEndOpen(arrayExistSameValue, 89));

二分查找算法拓展一 lower_bound 和upper_bound

• 查找第一个大于等于value的值的位置。（C++ STL的 lower_bound实现了该算法。 Java leftMost）
• 查找第一个大于value的值位置。（C++ STL的upper_bound实现了该算法。Java Left）

算法模块

    /*** 二分查找模板* * @param array* @param value* @return*/public static int binarySearchTemplate(int[] array, int value) {int start = 0;int end = array.length - 1;while (start <= end) {int mid = (start + end) >>> 1;int midValue = array[mid];if (value < midValue) { // end = mid - 1;} else if (midValue < value){start = mid + 1;} else {// todo 带补充的语句, 以下三选一// return mid;// end = mid - 1;// start = mid + 1;}}return start;}

• return mid; // 和默认的二分查找法相同，返回首次对半找到的值的index

• end = mid - 1; // 返回第一个大于等于value的值的位置。

  ​ 存在等于value的元素时，查找区间一致往左移动。

• start = mid + 1 // 返回第一个大于value的值位置

  ​ 存在等于value的元素时，查找区间一致往右移动。

二分查找算法拓展二

    /***  相同数查找*  0	1	2	3	4	5	6	7	8*  1, 32, 32, 56, 78, 89, 89, 89, 122*/

lower_bound 返回第一个大于等于value的值的index 。 例子：返回的值为5

upper_bound 返回第一个大于value的值的index。 例子：返回的值为8

拓展二:

lower_bound - 1 返回最后一个小于value的值的index。 例子：返回的值为4

upper_bound - 1 返回最后一个小于等于value的值的index。例子：返回的值为7

二分查找法的应用

• x < 89 的范围 0… lower_bound - 1

• x <= 89 的范围 0…upper_bound - 1

• x > 89 upper_bound… 无穷

• x >= 89 lower_bound … 无穷

• == 89的数量 upper_bound - lower_bound

将x替换为n时

• x< n 的范围 0… lower_bound - 1

• x<= n 的范围 0…upper_bound - 1

• x > n upper_bound… 无穷

• x=> n lower_bound … 无穷

• x== n 的数量 upper_bound - lower_bound

Java二分查找源码解析

返回值说明：

• 如果存在包含value，直接返回value的index
• 如果不存在，返回-(insertion point) - 1。 insertion point是指可以插入的元素。 减一的原因：区分位置0.

    public static int binarySearch(int[] a, int fromIndex, int toIndex,int key) {rangeCheck(a.length, fromIndex, toIndex);return binarySearch0(a, fromIndex, toIndex, key);}// Like public version, but without range checks.private static int binarySearch0(int[] a, int fromIndex, int toIndex,int key) {int low = fromIndex;int high = toIndex - 1;while (low <= high) {int mid = (low + high) >>> 1;int midVal = a[mid];if (midVal < key)low = mid + 1;else if (midVal > key)high = mid - 1;elsereturn mid; // key found}return -(low + 1);  // key not found. // low 表示第一个大于key的元素}

代码实现

默认实现

    /*** 标准二分查找法, 在一个数据找找寻value。** @param array 数组 升序排序* @param value 要找的数* @return 如果数组存在与value值相等的元素时，返回首次对半找到的值的index；否则返回-1*/public static int binarySearch(int[] array, int value) {int start = 0, end = array.length - 1;  // [start, end] 区间，start和end都能取得while (start <= end) {int mid = (start + end) >>> 1;if (array[mid] < value) {start = mid + 1;} else if (value < array[mid]) {end = mid - 1;} else {return mid;}}return -1;}

单元测试

    @Testpublic void testBinarySearch() {// 数据长度为单数 9int[] arraSingle = {1, 32, 34, 56, 78, 79, 89, 99, 122};Assert.assertEquals(0, BinarySearch.binarySearch(arraSingle, 1));Assert.assertEquals(4, BinarySearch.binarySearch(arraSingle, 78));Assert.assertEquals(2, BinarySearch.binarySearch(arraSingle, 34));Assert.assertEquals(8, BinarySearch.binarySearch(arraSingle, 122));// 数据长度为双数int[] arraySouble = {1, 32, 34, 56, 78, 79, 89, 99, 122, 352};Assert.assertEquals(0, BinarySearch.binarySearch(arraySouble, 1));Assert.assertEquals(4, BinarySearch.binarySearch(arraySouble, 78));Assert.assertEquals(2, BinarySearch.binarySearch(arraySouble, 34));Assert.assertEquals(8, BinarySearch.binarySearch(arraySouble, 122));Assert.assertEquals(9, BinarySearch.binarySearch(arraySouble, 352));/***  相同数查找*  1, 32, 32, 56, 78, 89, 89, 89, 122*  0	1	2	3	4	5	6	7	8*/int[] arrayExistSameValue = {1, 32, 32, 56, 78, 89, 89, 89, 122};Assert.assertEquals(6, BinarySearch.binarySearch(arrayExistSameValue, 89));/***  相同数查找*  1, 32, 32, 32, 86*  0	1	2	3	4*/int[] arrayExistSameValue2 = {1, 32, 32, 32, 86};Assert.assertEquals(2, BinarySearch.binarySearch(arrayExistSameValue2, 32));// 不存在数查找int[] arraySouble2 = {1, 32, 34, 56, 78, 79, 89, 99, 122, 352};Assert.assertEquals(-1, BinarySearch.binarySearch(arrayExistSameValue2, 2));Assert.assertEquals(-1, BinarySearch.binarySearch(arrayExistSameValue2, -1));Assert.assertEquals(-1, BinarySearch.binarySearch(arrayExistSameValue2, Integer.MAX_VALUE));Assert.assertEquals(-1, BinarySearch.binarySearch(arrayExistSameValue2, 70));}

lower_bound

    /*** 返回第一个大于等于Value的值** @param array* @param value* @return*/public static int binarySearchLowerBound(int[] array, int value) {int start = 0;int end = array.length - 1;while (start <= end) {int mid = (start + end) >>> 1;int midValue = array[mid];if (value < midValue) {end = mid - 1;} else if (midValue < value) {start = mid + 1;} else { // ==end = mid - 1;}}return start;}

单元测试

   @Testpublic void binarySearchLowerBound() {/***  相同数查找*  1, 32, 32, 56, 78, 89, 89, 89, 122*  0	1	2	3	4	5	6	7	8*/int[] arrayExistSameValue = {1, 32, 32, 56, 78, 89, 89, 89, 122};Assert.assertEquals(0, BinarySearch.binarySearchLowerBound(arrayExistSameValue, 0));Assert.assertEquals(1, BinarySearch.binarySearchLowerBound(arrayExistSameValue, 32));Assert.assertEquals(4, BinarySearch.binarySearchLowerBound(arrayExistSameValue, 57));Assert.assertEquals(5, BinarySearch.binarySearchLowerBound(arrayExistSameValue, 89));Assert.assertEquals(8, BinarySearch.binarySearchLowerBound(arrayExistSameValue, 122));Assert.assertEquals(9, BinarySearch.binarySearchLowerBound(arrayExistSameValue, Integer.MAX_VALUE));int[] arrayExistSameValue2 = {1, 32, 32, 56, 90, 90, 90, 90, 122};Assert.assertEquals(4, BinarySearch.binarySearchLowerBound(arrayExistSameValue2, 90));}

UpperBound

    /*** 返回第一个大于Value的值** @param array* @param value* @return*/public static int binarySearchUpperBound(int[] array, int value) {int start = 0;int end = array.length - 1;while (start <= end) {int mid = (start + end) >>> 1;int midValue = array[mid];if (value < midValue) {end = mid - 1;} else if (midValue < value) {start = mid + 1;} else {start = mid + 1;}}return start;}

单元测试

@Test
public void binarySearchUpperBound() {/***  相同数查找*  1, 32, 32, 56, 78, 89, 89, 89, 122*  0  1  2  3  4  5  6  7  8*/int[] arrayExistSameValue = {1, 32, 32, 56, 78, 89, 89, 89, 122};Assert.assertEquals(0, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 0));Assert.assertEquals(3, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 32));Assert.assertEquals(4, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 57));Assert.assertEquals(8, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 89));Assert.assertEquals(9, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 122));Assert.assertEquals(9, BinarySearch.binarySearchUpperBound(arrayExistSameValue, Integer.MAX_VALUE));int[] arrayExistSameValue2 = {1, 1,1,1};Assert.assertEquals(4, BinarySearch.binarySearchUpperBound(arrayExistSameValue2, 1));
}

确定相同元素的个数

@Test
public void testBinarySearchBoundEqualsNum() {/***  相同数查找*  1, 32, 32, 56, 78, 89, 89, 89, 122*  0  1  2  3  4  5  6  7  8*/int[] arrayExistSameValue = {1, 32, 32, 56, 78, 89, 89, 89, 122};Assert.assertEquals(3, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 89)- BinarySearch.binarySearchLowerBound(arrayExistSameValue, 89));Assert.assertEquals(0, BinarySearch.binarySearchUpperBound(arrayExistSameValue, 4)- BinarySearch.binarySearchLowerBound(arrayExistSameValue, 4));int[] arrayExistSameValue2 = {1, 1,1,1};Assert.assertEquals(4, BinarySearch.binarySearchUpperBound(arrayExistSameValue2, 1)- BinarySearch.binarySearchLowerBound(arrayExistSameValue, 1));}