跳转到主内容
趣航编程网 - 趣学编程,启航技术之路!

二分法查找介绍

二分法查找今天讲一下“二分法查找”,二分法查找思路就是在一段顺序数组中,每次和某一段数组中间数比大小。二分法查找的缺点是数组必须是顺序的(我以由小到大排序数据为例),优点是查询效率极高,时间复杂度是log2n。这种查找方式越是在大数据下,效果越是明显。下面附上源代码和单元测试,源代码包含两种算法,一种是循环一种是递归,大家多参考:

源代码:

///

/// 使用二分法查找一个数据所在问题位置。(递归方法)

/// 数组必须是从小到大排序的,如果是未排序数据可使用类/// 或者类进行排序。

/// 如果要查找的值在数组中不存在,返回-1。

///

/// 数组/// 要查找的值/// 返回第几个,如果要查找的值在数组中不存在,返回-1public static int Search(int[] array, int value){if (array == null) { throw new ArgumentException("array is null"); }if (array[array.Length - 1] == value) { return array.Length - 1; }return Search(array, 0, array.Length - 1, value);}private static int Search(int[] array, int beginIndex, int endIndex, int value){int middle = (beginIndex + endIndex) / 2;if (endIndex == beginIndex){ return array[beginIndex] == value ? beginIndex : -1; }else if (endIndex == beginIndex + 1){if (array[beginIndex] == value) { return beginIndex; }else if (array[endIndex] == value) { return beginIndex; }else { return -1; }}if (array[middle] == value){ return middle; }else if (array[middle] > value){ return Search(array, beginIndex, middle, value); }else if (array[middle] < value){ return Search(array, middle, endIndex, value); }return -1;}/// /// 使用二分法查找一个数据所在问题位置。(循环方法)

/// 数组必须是从小到大排序的,如果是未排序数据可使用类/// 或者类进行排序。

/// 如果要查找的值在数组中不存在,返回-1。

///

/// 数组/// 要查找的值/// 返回第几个,如果要查找的值在数组中不存在,返回-1public static int Search2(int[] array, int value){int beginIndex = 0;int endIndex = array.Length - 1;while (true){if (endIndex - beginIndex <= 1){if (value == array[beginIndex]) { return beginIndex; }if (value == array[endIndex]) { return endIndex; }{ return -1; }}int middle = (beginIndex + endIndex) / 2;if (value < array[middle]) { endIndex = middle; }if (value == array[middle]) { return middle; }if (value > array[middle]) { beginIndex = middle; }}}

单元测试:

[TestMethod()][DeploymentItem("ZjyWorkCodeLibrary.dll")]public void SearchTest(){Random random = new Random();int[] array2 = new int[100];for (int i = 0; i < 100; i++){array2[i] = random.Next(0, 1000);}int[] array3 = BitmapSort.Sort(array2);for (int i = 0; i < array3.Length; i++){Assert.AreEqual(BinarySearch.Search(array3, array3[i]), i);Assert.AreEqual(BinarySearch.Search2(array3, array3[i]), i);}Assert.AreEqual(BinarySearch.Search(array3, 9999), -1);Assert.AreEqual(BinarySearch.Search2(array3, 9999), -1);}更多二分法查找介绍相关文章请关注PHP中文网!

相关文章