算法—8.有序数组中的二分查找

1.具体算法

/** * 算法3.2 二分查找（基于有序数组） * Created by huazhou on 2015/11/29. */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;  }  public boolean isEmpty() {    return size() == 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 int rank(Key key){    int lo = 0, 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 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 void delete(Key key){    if (isEmpty()) return;    // compute rank    int i = rank(key);    // key not in table    if (i == N || keys[i].compareTo(key) != 0) {      return;    }    for (int j = i; j < N-1; j++) {      keys[j] = keys[j+1];      vals[j] = vals[j+1];    }    N--;    keys[N] = null; // to avoid loitering    vals[N] = null;    // resize if 1/4 full    if (N > 0 && N == keys.length/4) resize(keys.length/2);  }}

海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理：https://www.xlkjsw.com

原标题：算法—8.有序数组中的二分查找

关键词：