精华内容
下载资源
问答
  • 二分搜索

    2017-10-29 20:36:18
    二分搜索

    一、适用条件

     二分搜索采用分治法。分治法基本思想是将一个规模为n的问题分解为k个规模较小的子问题。其适用条件为:

    • 原问题在规模缩小到一定程度时很容易求解
    • 原问题可以分解为若干个规模较小的子问题
    • 子问题互相独立且与原问题相同
    • 子问题的解可合并为原问题的解

    二、算法实现

      问题:从给定的已排好序的n个元素a[0:n1]中找出一个特定元素x。
      解决该问题可以使用递归和非递归两种方式

    2.1递归方法

    
     1. template<typename T>
     2. int BinarySerach(T a[], int left, int right,const T& x)
     3. {
     4.     while(left <= right) {
     6.         int middle = (left + right) / 2;
     5.         if (a[middle] > x) 
     6.             return BinarySearch(a, left, middle - 1, x);
     7.         if (a[middle] < x)
     8.             return BinarySearch(a, middle + 1, right, x);
     9.         else 
     10.            return middle;
     11.     }
     12.     return -1;
     12. }     
    

    2.2非递归方法

    
     1. template<typename T>
     2. int BinarySearch(T a[], const T& x, int n)
     3. {
     4.     int left = 0; int right = n - 1;
     5.     while (left <= right) {
     6.         int middle = (left + right) / 2;
     7.         if (a[middle] == x) return middle;
     8.         if (a[middle] < x) left = middle + 1;
     9.         else right = middle - 1;
     10.     }
     11.     return -1;
     12. }
    

    2.3寻找下界

    
     1. template<typename T>
     2. int BinarySearch(T a[], const T& x, int n)
     3. {
     4.     if (rignt < left) return -1;
     4.     int left = 0; int right = n - 1;
     5.     int middle = (left + right + 1) / 2;
     5.     while(right >= left) {
     6.         if(a[middle] < x) left = middle;
     7.         else right = middle - 1;
     8.         middle = (left + right + 1) / 2;
     9.     }
     10.    return middle;
     11. }
    

      求中间索引采用向上取整的原因是防止陷入死循环。二分法求上界的算法与此相似,也是采用半边检索方式寻找目标值。
      二分检索缺点是检索序列必须为有序序列,当检索序列中含有重复值时需搜索出上界和下界,中间的范围为所求值。

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,467
精华内容 6,186
关键字:

二分搜索