Go语言视频零基础入门到精通

admin

    二分查找算法是在有序数组中用到的较为频繁的一种算法，在未接触二分查找算法时，最通用的一种做法是，对数组进行遍历，跟每个元素进行比较，其时间为O(n).但二分查找算法则更优，因为其查找时间为O(lgn)，譬如数组{1， 2， 3， 4， 5， 6， 7， 8， 9}，查找元素6，用二分查找的算法执行的话，其顺序为：
    1.第一步查找中间元素，即5，由于5<6，则6必然在5之后的数组元素中，那么就在{6， 7， 8， 9}中查找，
    2.寻找{6， 7， 8， 9}的中位数，为7，7>6，则6应该在7左边的数组元素中，那么只剩下6，即找到了。
    二分查找算法就是不断将数组进行对半分割，每次拿中间元素和goal进行比较。


  #include
  <
  iostream
  >
  

  using
  namespace
   std;


  //
  二分查找
  

  int
   binary_search(
  int
  *
   a,
  int
   len,
  int
   goal);


  int
   main()
{

      const
  int
   LEN
  =
  10000
  ;

      int
   a[LEN];

      for
  (
  int
   i
  =
  0
  ; i
  <
   LEN; i
  ++
  )
        a
  =
   i
  -
  5000
  ;

      int
   target
  =
  0
  ;

      int
   index
  =
   binary_search(a, LEN, target);


      if
  (index
  !=
  -
  1
  )
        cout
  <<target
  <<
  "
  在数组中的下标为
  "
  <<
  index
  <<
  endl;

      else
  
        cout
  <<
  "
  不存在
  "
  <<target
  <<
  endl;

      return
  0
  ;
}


  int
   binary_search(
  int
  *
   a,
  int
   len,
  int
   goal)
{

      int
   low
  =
  0
  ;

      int
   high
  =
   len
  -
  1
  ;

      while
  (low
  <=
   high)
    {

          int
   middle
  =
   (high - low) / 2 + low
  ; // 直接使用(high + low) / 2 可能导致溢出

          if
  (a[middle]
  ==
   goal)

              return
   middle;

          //
  在左半边
  

          else
  if
  (a[middle]
  >
   goal)
            high
  =
   middle
  -
  1
  ;

          //
  在右半边
  

          else
  
            low
  =
   middle
  +
  1
  ;
    }

      //
  没找到
  

      return
  -
  1
  ;
}