Introduction to binary search

Binary search

Today we will talk about "binary search". The idea of ​​binary search is to compare the size with the middle number of a certain array in a sequential array each time. The disadvantage of binary search is that the array must be sequential (I take the data sorted from small to large as an example). The advantage is that the query efficiency is extremely high and the time complexity is log2n. The more this search method is used in big data, the more obvious the effect will be. The source code and unit test are attached below. The source code contains two algorithms, one is loop and the other is recursive. Please refer to it:
Source code:

                                                                                                                                                                                                                                     . (Recursive method)//// The array must be sorted from small to large. If it is unavailable data, it can be used & lt; see cref = "bitmapsort"/& gt; >Classes are sorted.
                     /// If the value to be found does not exist in the array, return -1.
                                                                                                          param>
                                                                                                                                                                ,,,,,,,,,,,,,,,,,,, if (array == null) { throw new ArgumentException("array is null"); }
            if (array[array.Length - 1] == value) { return array.Length - 1; }
                                                                                                 0, array.Length - 1, value);
                                                                   private static int Search(int[] array, int beginIndex, int endIndex, int value)                                                                          if ( endIndex == beginIndex)
                                                                                                                                                       == value) { return beginIndex; }
                                                                                                                                                                                                                                                                                    [middle] > value)
                                                                                                                                                               ​return -1;
                                                                                             (Loop method)
          /// The array must be sorted from small to large. If it is unsorted data, you can use the class
                                      or                                                >Classes are sorted.
                     /// If the value to be found does not exist in the array, return -1.
                                                                                                          Param & gt;
/// & lt; Return & gt; return to the first few, if the value you want to find does not exist in the array, return to -1 & lt;/return;
{
int beginIndex = 0;
int endIndex = array.Length - 1;
while (true)
if (endIndex - Index begin                                                                                                                                                                                                                                     if (value == array[beginIndex]) { return beginIndex; }
                                                                                                                                         endIndex) / 2;
               if (value                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            {
               array2[i] = random.Next(0, 1000);
           }
           int[] array3 = BitmapSort.Sort(array2);
           for (int i = 0; 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中文网！