首页 > 代码库 > page61-将二分查找重写为一段面向对象的程序
page61-将二分查找重写为一段面向对象的程序
1 将二分查找重写为一段面向对象的程序 （用于在整数集合中进行查找的一种抽象数据类型）
public class StaticSETofInts 【API】
StaticSETofInts(int[] a )根据 a[]中的所有值创建一个集合
boolean contains(int key) key是否存在于集合中。
【数据实现】
import java.util.Arrays;public class StaticSETofInts { private int[] a; public StaticSETofInts(int[] keys){ a = new int[keys.length]; for (int i = 0; i < keys.length; i++) a[i] = keys[i];//保护性复制 Arrays.sort(a); } public boolean contains(int key){ return rank(key) != -1; } private int rank(int key){//二分查找 int low = 0; int high = a.length -1; while(low <= high){ //要么存在于a[low..high]中， 要么不存在。 int mid = (low + high) /2; if(key < a[mid]) high = mid -1; else if(key > a[mid]) low = mid + 1; else return mid; } return -1; }}
【典型测试用例】
public class Whitelist { public static void main(String[] args) { int[] w = new In(args[0]).readAllInts(); StaticSETofInts set = new StaticSETofInts(w); while(!StdIn.isEmpty()){ int key = StdIn.readInt(); if(!set.contains(key)) System.out.println(key); } }}
【打印结果】
page61-将二分查找重写为一段面向对象的程序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。