首页 > 代码库 > java数据结构学习（一）之二分查找

java数据结构学习（一）之二分查找

2024-07-16 06:21:04   219人阅读

     二分查找法与我们在孩童时期玩过的猜数的游戏一样，这个游戏里一个朋友会让你猜他正想的一个1至100的数，当你猜了一个数后，他会告诉你三种选择的一个：你猜的比她想的大，或小，或猜中了。为了能用最少的次数猜中，必须从50开始猜，如果她说你猜的太小，则推出那个数在51-100之间，所以下一次猜75（(51+100)/2）,如果她说有些大，那你就会在51-74之间才，下一次猜（51+74）/2=62。直到猜中她所给的数。

下面给出我们猜1-100的数，key为33的过程：

　　

只需7次就可以猜中答案。下面我们给出二分查找的代码：

public class BinarySearch {    private long[] a;    private int nelems;    public BinarySearch(int max){        a = new long[max];        nelems = 0;    }    //返回数组的长度    public int size(){        return nelems;    }    /**     * 二分查找算法关键代码     * @return     */    public int binarySearch(long searchKey){        int low = 0;        int high = nelems-1;        int curIn;        while(true){            curIn = (low + high)/2;//划分范围的点            if(a[curIn] == searchKey){//幸运判断，很幸运正好猜中                return curIn; //返回要猜的数的位置            }else if(low > high){//范围不存在                return nelems;//没找到，返回数组的长度            }else{                if(searchKey > a[curIn]){                    low = curIn + 1;                }else{                    high = curIn - 1;                }            }        }    }          /**     *      * 在有序数组里面插入数     * @param args     */    public void insertOrderArray(long value){        int i;        for(i=0;i<nelems;i++){//遍历有序数组里面的元素与插入的数进行比较            if(a[i] > value){//如果有序数组里面的某一个数比插入的数大，则结束遍历                break;            }        }                //插入的位置i,及i后面到的元素都要向右移动，腾出一个插入位置        for(int k=nelems;k>i;k--){            a[k] = a[k-1];//a[10]=a[9],a[9] = a[8]插入点后面的都向右移动一个位置        }        a[i] = value;//移动后腾出位置插入要插入的数        nelems++;    }    /**     * 删除有序数组里面的数     */    public boolean delete(long key){        int i = binarySearch(key);//返回找到的数字数组下标        if(i==nelems){            return false;        }else{            int j;            for(j=i;j<nelems;j++){                a[j] = a[j+1];//向前移动            }            nelems--;//数组长度减少            return true;                    }    }    /**     * 显示数组中的数     */    public void display(){        System.out.println("***************");        for(int j=0;j<nelems;j++){            System.out.print(a[j]+" ");            System.out.print("");        }    }    public static void main(String[] args){        int maxSize = 100;        BinarySearch arr = new BinarySearch(maxSize);        arr.insertOrderArray(30);        arr.insertOrderArray(12);        arr.insertOrderArray(15);        arr.insertOrderArray(10);        arr.insertOrderArray(90);        arr.insertOrderArray(100);        arr.insertOrderArray(101);        arr.insertOrderArray(80);        System.out.println("##############");        arr.display();        long keySearch = 102;        if(arr.binarySearch(keySearch) != arr.size()){//上面返回值为没找到返回nelems长度            System.out.println("找到"+keySearch);        }else{            System.out.println("没有找到"+keySearch);        }        arr.delete(30);        arr.delete(100);        arr.display();    }}

 

 

 

 


联系
我们