【查找算法之折半查找算法】

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略。基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。每找一次目标范围就缩小一半，缺点是：集合中元素必须是有序的，升序降序都行。

 

折半查找法：

在有序按照升序排列的表中，把待查找数据值与查找范围的中间元素值进行比较，会有三种情况出现：

1、待查找数据值与中间元素值正好相等，则返回中间元素值的索引。

2、待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行1），

              直到找到相等的值。

3、待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行1），

             直到找到相等的值。

4、如果最后找不到相等的值，则返回错误提示信息。

      按照二叉树来理解：中间值为二叉树的根，前半部分为左子树，后半部分为右子树。

      折半查找法的查找次数正好为该值所在的层数。等概率情况下，约为log2(n+1)-1

 

代码示例：

方案一、非递归查找

/**

* 假设升序排列

* @param srcArray  集合

* @param des  待查找元素

* @return 也许能找到,也许找不到,返回位置

*/

public static int binarySearch(Integer[] srcArray, int des) {

   int low = 0;                     //第一个元素下标为0

   int high = srcArray.length - 1; //最后一元素位置下标为长度减1

 

   while ((low <= high) && (low <= srcArray.length - 1)

           && (high <= srcArray.length - 1)) {

   

    //左移一位,相当于除以2,得到最中间的元素

       int middle = (high + low) >> 1;

           

       if (des == srcArray[middle]) {

        //中间元素刚好等于待查找元素

           return middle;

       } else if (des < srcArray[middle]) {

        //因为升序排列,中间元素大于待查找元素,因因此待查找元素如果存在,只会落在左半边元素中

           high = middle - 1;

       } else {

        //因为升序排列,中间元素小于待查找元素,因因此待查找元素如果存在,只会落在右半边元素中

           low = middle + 1;

       }

   }

   return -1;

}

 

 

方案二、递归查找

// 递归法(升序排列的集合)

int IterBiSearch(int data[], int target, int begin, int last) {

int mid = (begin + last) / 2;

if (target == data[mid]) {

return mid;

} else if (target < data[mid]) {

return IterBiSearch(data, target, begin, mid - 1);

} else if (target > data[mid]) {

return IterBiSearch(data, target, mid + 1, last);

}

return -1;

}