二分查找的两种实现方式
namespace DataStructureAndAlgorithm.Search { /// <summary> /// 二分查找算法 /// </summary> public class BinarySearch { public static void Test() { int[] arrs = { 1,3,7,23,44,55 }; int index = SearchWhile(arrs, 23); index = SearchDiGui(arrs, 0, arrs.Length - 1, 23); index = SearchWhile(arrs, 100); index = SearchDiGui(arrs, 0, arrs.Length - 1, 100); index = SearchWhile(arrs, 44); index = SearchDiGui(arrs, 0, arrs.Length - 1, 44); } /// <summary> /// 方法一:用While实现 /// </summary> /// <param name="arrs"></param> /// <param name="val"></param> /// <returns></returns> public static int SearchWhile(int [] arrs,int val) { int leftIndex = 0; int rightIndex = arrs.Length - 1; while (leftIndex <= rightIndex) { int midIndex = (leftIndex + rightIndex) / 2; int midVal = arrs[midIndex]; if (val > midVal) { //向右查找 leftIndex = midIndex + 1; } else if (val < midVal) { //向左查找 rightIndex = midIndex - 1; } else if (val == midVal) { //找到了 return midIndex; } } //没找到 return -1; } /// <summary> /// 方法二:用递归实现 /// </summary> /// <param name="arrs"></param> /// <param name="leftIndex"></param> /// <param name="rightIndex"></param> /// <param name="val"></param> /// <returns></returns> public static int SearchDiGui(int[] arrs,int leftIndex,int rightIndex,int val) { if (leftIndex > rightIndex) { //没找到 return -1; } int midIndex = (leftIndex + rightIndex) / 2; if (val == arrs[midIndex]) { //找到了 return midIndex; } else if (val > arrs[midIndex]) { //向右查找 return SearchDiGui(arrs, midIndex + 1, rightIndex, val); } else { //向左查找 return SearchDiGui(arrs, leftIndex, midIndex - 1, val); } } } }