算法3.2二分查找（基于有序数组）

《算法》笔记导航

《算法》中文第四版P239
2020.7.30
@Stream_

`public class BinarySearchST <Key extends Comparable<Key>,Value>`

每次添加（修改）键值对的时候，通过二分法找到合适的位置，添加（修改），保持数组有序

一、变量，方法，类及其作用

1.变量

private Key[] keys;
储存key值，和value值一一对应
private Value[] vals;
储存value值，和key值一一对应
private int N;
键值对的个数

2.方法

2.1构造方法与对数组的基本查找

public BinarySearchST(int capacity)
创建指定大小的数组（动态调整数组大小的方法请看：算法1.1下压栈（能够动态调整数组大小的实现））
public int size()
返回键值对的个数
private boolean isEmpty()
查看键值对个数是否为0，为0则返回true

2.2进行二分查找

public int rank(Key key)
如果查找到匹配的键值对，则返回键值对在数组的位置。如果没查找到，则返回比key值小的个数（也就是添加的位置），通过对返回值的检测，可得知是否有完全一样的key值。
将中间值mid和key值进行比较，如果mid比key值小，则在key值左侧寻找，如果比key值大，则在key值右侧寻找，进行循环查找。

2.3获取值和添加修改值

public Value get(Key key)
用rank查找key值对应的value值，如果没有则返回null
public void put(Key key,Value val)
先用rank查找key值，如果存在key则修改它对应的value值，如果没有，则在该位置添加键值对（因为rank返回的值是比key值要小的键值对的个数）

二、算法的实现

public class BinarySearchST <Key extends Comparable<Key>,Value>{
    private Key[] keys;
    private Value[] vals;
    private int N;

    public BinarySearchST(int capacity){
        keys=(Key[]) new Comparable[capacity];
        vals=(Value[]) new Object[capacity];
    }
    public int size(){
        return N;
    }
    private boolean isEmpty(){
        return N==0;
    }
    public Value get(Key key){
        if(isEmpty()){
            return null;
        }
        int i=rank(key);
        if(i<N&&keys[i].compareTo(key)==0){
            return vals[i];
        }
        else{
            return null;
        }
    }
    public void put(Key key,Value val){
        int i=rank(key);
        if(i<N&&keys[i].compareTo(key)==0){
            vals[i]=val;
            return;
        }
        for(int j=N;j>i;j--){
            keys[j]=keys[j-1];
            vals[j]=vals[j-1];
        }
        keys[i]=key;
        vals[i]=val;
        N++;
    }
    public int rank(Key key){
        int lo=0;
        int hi=N-1;
        while(lo<=hi){
            int mid=lo+(hi-lo)/2;
            int cmp=key.compareTo(keys[mid]);
            if(cmp<0){
                hi=mid-1;
            }
            else if(cmp>0){
                lo=mid+1;
            }
            else{
                return mid;
            }
        }
        return lo;
    }

}

三、算法的使用

public static void main(String[] args) {
        int[] nums={11,1,15,4,2,16,8,13,7,3,10,9,5,12,6,14};

        BinarySearchST bs=new BinarySearchST(20);

        for(int i=0;i<nums.length;i++){
            bs.put(i,nums[i]);
        }

        for(int i=0;i< nums.length;i+=3){
            System.out.print(bs.get(i)+" ");
        }
    }

四、算法的优劣、注意和使用场景

1.动态调整数组的方法请查看：算法1.1下压栈（能够动态调整数组大小的实现）
2.put()方法会在插入新元素前将所有较大的键向后移动一格
3.不能用于链表，因为二分查找需要数次迅速找到中间值并进行比较，需要直接访问中间值
4.优点：最优的查找效率和空间需求，能够进行有序性相关的操作
5.缺点：插入操作很慢。对大数组来说，动态调整数组更慢

《算法》笔记导航
渣渣菜鸡，难免错误，请友善讨论
非商用转载需注明作者及文章链接来源，私信告知后无需我回复即可直接转载