学校网站建设过程,网站建设及管理,我想做个百度网站怎么做的,查询网站入口二分查找算法算法总结
算法描述
该算法属于查找算法。当需要从有序数组中查找某一元素时#xff0c;可以使用该算法进行查找。#xff08;本文章假设数组是升序排列的数组#xff09;
算法思想
每次进行对半查找#xff0c;获取中间元素值#xff0c;然后与目标值进行…二分查找算法算法总结
算法描述
该算法属于查找算法。当需要从有序数组中查找某一元素时可以使用该算法进行查找。本文章假设数组是升序排列的数组
算法思想
每次进行对半查找获取中间元素值然后与目标值进行比较。
如果目标元素等于中间值则查找成功返回中间元素的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));}
