二分法查找介绍

二分法查找

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

       ///

       /// 使用二分法查找一个数据所在问题位置。（递归方法）
       /// 数组必须是从小到大排序的，如果是未排序数据可使用类
       /// 或者类进行排序。
       /// 如果要查找的值在数组中不存在，返回-1。
       ///

       /// 数组
       /// 要查找的值
       /// 返回第几个，如果要查找的值在数组中不存在，返回-1
       public 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。
       ///

       /// 数组
       /// 要查找的值
       /// 返回第几个，如果要查找的值在数组中不存在，返回-1
       public 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中文网！