JAVA基础之二分(折半)查找法

JAVA基础之二分查找

简介

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

方法

首先,假设表中元素按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;
否则利用中间位置记录将表分为前\后两个字表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一字表.
重复以上过程,直到找到满足条件的记录,使查找成功,或直到字表不存在为止,此时查找不成功.

java代码示例

public static void main(String[] args){
    int[] array = new int[] {2, 3, 6, 7, 8, 9, 10, 11, 12, 13};
    int max = array.length - 1;
    int min = 0;

    int key = 22;
    int mid = (min + max)/2;

    while(key != array[mid]) {
        if(key > array[mid]) {
            min = mid + 1;
        }else if(key < array[mid]) {
            max = mid - 1;
        }
        //挪动完角标后  还要进行折半操作
        mid = (min + max)/2;

        //当最大角标 小于 最小角标的时候 说明数组中没有这个数
        if(max < min) {
            // 进到这里 说明没这个数
            mid = -1;
            break;
        }
    }
    System.out.println("这个数的角标是:" + mid);
}