您当前的位置： 首页 > 学无止境 > 心得笔记 网站首页心得笔记

javase第三季学习笔记-二分查找算法

发布时间：2017-08-10 15:32:50编辑：雪饮阅读（）

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

有序性：因为二分查找每次将数组折半，然后根据要查的值来比较是在小数值集合哪一边进行查找，还是在大数值集合哪一边进行查找。那么如果待查表不是有序的，则这种折半查找算法则是无意义的了。

技术细节：

(数组的最小下标值+数组最大下标值)/2得到第一个待查找的下标，然后将待查找的值与该下标对应的值对比，若相等则找到了，若不相等则判断待查找的值与该下标对应的值比较大小，根据比较结果决定下次查找范围是在该下标左边还是右边，例如确定为在左边后，就(左边最小下标+左边最大下标)/2再次得到一个查找点。然后和上面步骤一样。一直如此，直到查到。

示例代码：

package com.vince.bs;

 

import java.util.Arrays;

 

public class BinarySearchDemo {

 

    public static void main(String[] args) {

        //保证数组是有序的

        int [] number={2,2,0,8,7};

        Arrays.sort(number);

        int index=binarySearch(number,7);

        System.out.println(index);

 

 

    }

    //实现二分查找算法

    public static int binarySearch(int[] x,int n){

        int start=0;

        int end=x.length-1;

        int mid=-1;

        while(start<=end){

            mid=(start+end)/2;

            if(x[mid]==n){return mid;}

            else if(x[mid]<n){start=mid+1;}

            else{end=mid-1;}

        }

        return -1;

    }

 

}