c#二分查找的两种方式
2021-02-20 02:21
阅读：383
其实；两种方式的实现结果一样，却体现出了不同的思考过程；
地中方式，是在一个while循环中，每次从中间找，不断的去改变low 和 high的 位置，然后求他们的中间位置，知道low=high=0；如果还没有知道值，就直接返回-1；
////// 二分查找方式 /// /// /// /// public static int BinaySearch(int[] arr, int target) { int len = arr.Length; int low = 0; int high = len - 1; //一个while循环就搞定了； while (low high) { int middleIndex = (low + high) / 2; int middleValue = arr[middleIndex]; if (middleValue == target) { return middleIndex; } else if (target > middleValue) { //searching in right; low = middleIndex + 1; } else { //searching in left; high = middleIndex - 1; } } //没有找到直接就return return -1; }
然后，是利用我们递归的方式来实现的；如果没有找到，子改变地址，然后recursionly的去searching
////// 这样我们的二分查找的递归方式就出来了； /// 这个方式是我们用递归的方式来实现的； /// 不同的代码实现过程，体现了你不同的思考过程； /// /// /// /// /// /// public static int RecursionlyBinaySearch(int[] arr, int low, int high, int target) { int l = low; int h = high; if (l > h) return -1; int middleIndex = (l + h) / 2; int middleValue = arr[middleIndex]; if (middleValue == target) { //stop finding； return middleIndex; } else if (target > middleValue) { // finding in right; return RecursionlyBinaySearch(arr, middleIndex + 1, high, target); } else { //finding in left; return RecursionlyBinaySearch(arr, l, middleIndex - 1, target); } }
本来，想整一个第三种方式出来的；。。。。。。。。。。。只是本来；
第一种做法，有一个bug，你发现了吗？？？？而且！！！非常不明显；
详细的，请看这里；
https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html
这里还有更详细的介绍：
https://www.quora.com/Why-do-people-use-mid-low+-high-low-2-instead-of-low+high-2
评论
亲，登录后才可以留言！