二分查找是一种查询效率非常高的查找算法。又称折半查找。
算法思想
有序的序列,每次都是以序列的中间位置的数来与待查找的关键字进行比较,每次缩小一半的查找范围,直到匹配成功。
一个情景:将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
上代码
public class BinarySearchST<Key extends Comparable<Key>, Value> {
private Key[] keys;
private Value[] vals;
private int N;
public BinarySearchST(int cap) {
keys = (Key[]) new Comparable[cap];
vals = (Value[]) new Object[cap];
}
public int size() {
return N;
}
public Value get(Key key) {
if (isEmpty()) return null;
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0) {
return vals[i];
}
return null;
}
private 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 boolean isEmpty() {
return N == 0;
}
public void put(Key key, Value value) {
//查找键,找到更新值,否则创建新的元素
int i = rank(key);
if (i <= N && keys[i] == null) {
keys[i] = key;
vals[i] = value;
N++;
return;
} else if (i < N && keys[i].compareTo(key) == 0) {
vals[i] = value;
return;
}
for (int j = N; j > i; j--) {
keys[j] = keys[j - 1];
vals[j] = vals[j - 1];
keys[i] = key;
vals[i] = value;
N++;
}
}
}public class BinarySearchST<Key extends Comparable<Key>, Value> {
private Key[] keys;
private Value[] vals;
private int N;
public BinarySearchST(int cap) {
keys = (Key[]) new Comparable[cap];
vals = (Value[]) new Object[cap];
}
public int size() {
return N;
}
public Value get(Key key) {
if (isEmpty()) return null;
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0) {
return vals[i];
}
return null;
}
private 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 boolean isEmpty() {
return N == 0;
}
public void put(Key key, Value value) {
//查找键,找到更新值,否则创建新的元素
int i = rank(key);
if (i <= N && keys[i] == null) {
keys[i] = key;
vals[i] = value;
N++;
return;
} else if (i < N && keys[i].compareTo(key) == 0) {
vals[i] = value;
return;
}
for (int j = N; j > i; j--) {
keys[j] = keys[j - 1];
vals[j] = vals[j - 1];
keys[i] = key;
vals[i] = value;
N++;
}
}
}
二分查找要求序列必须有序,put方法是插入操作,插入元素也必须保证数组有序