Rumah > php教程 > PHP开发 > 二分法查找介绍

二分法查找介绍

高洛峰
Lepaskan: 2016-12-19 16:29:39
asal
1760 orang telah melayarinya

二分法查找

今天讲一下“二分法查找”,二分法查找思路就是在一段顺序数组中,每次和某一段数组中间数比大小。二分法查找的缺点是数组必须是顺序的(我以由小到大排序数据为例),优点是查询效率极高,时间复杂度是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中文网!

Label berkaitan:
sumber:php.cn
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Cadangan popular
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan