当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

二分(折半)查找算法

发表于: 2012-09-14   作者:128kj   来源:转载   浏览:
摘要: 二分查找又称折半查找,它是一种效率较高的查找方法。   折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。通过一次比较,将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数,提高查找效率。但是,折半查找的先决条件是查
二分查找又称折半查找,它是一种效率较高的查找方法。

  折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。通过一次比较,将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数,提高查找效率。但是,折半查找的先决条件是查找表中的数据元素必须有序。


  折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

算法步骤描述
① 首先确定整个查找区间的中间位置 mid = ( low + high )/ 2

② 用待查关键字值与中间位置的关键字值进行比较;

  若相等,则查找成功

  若大于,则在后(右)半个区域继续进行折半查找

  若小于,则在前(左)半个区域继续进行折半查找

③ 对确定的缩小区域再按折半公式,重复上述步骤。

最后,得到结果:要么查找成功, 要么查找失败。折半查找的存储结构采用一维数组存放。

public class Test{
  public static < T  extends Comparable < ? super T>> int binarySearch(T [] array,T key){
        int low = 0;
        int high = array.length-1;
        while(low <= high){
            int mid = (low + high)/2;
            if(array[mid].compareTo(key)< 0){
                low = mid + 1;
            }else if(array[mid].compareTo(key)>0){
                high = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
     public static void main(String args[]){
        Integer  a[]={1,2,3,4,5,6,7,8,9};
        int k=binarySearch(a,7);
        System.out.println("k="+k);
    }
}

二分(折半)查找算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
#include <stdio.h> #define MAXL 100 typedef int KeyType; typedef char InfoType[10]; typ
代码部分: #include <stdio.h> #define MAXL 100 typedef int KeyType; typedef char InfoTy
#include <stdio.h> #define MAXL 100 typedef int KeyType; typedef char InfoType[10]; typ
/* 折半查找 */ class TwoSearch { //折半查找可以提高效率,但必须得保证是有序的数组 public stat
#include <stdio.h> #define MAXL 100 typedef int KeyType; typedef char InfoType[10]; typ
排序算法二:二分(折半)插入排序算法 声明:引用请注明出处http://blog.csdn.net/lg1259156776/
编程之美在于算法之美,先来看看二分查找的算法: 隐藏条件:二分查找必须是有序的,从小到大,或从
二分查找 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为
二分查找算法前提有2个:1.必须采用顺序存储结构,2.必须按关键字有序排列。时间复杂度为O(logn)。
算法-查找之二二分查找 顺序查找【算法-查找之一】顺序查找是最简单的查找策略,易于分析,适用于小
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号