BlockSearch

package Search;
import java.util.ArrayList;
public class BlockSearch {
	private int[] index;//建立索引
	private ArrayList[] list;
	
	//初始化索引列表
	public BlockSearch(int[] index)
	{
		if(index!=null && index.length!=0)
		{
			this.index=index;
			this.list=new ArrayList[index.length];
			
			for(int i=0;i<list.length;i++)
				list[i]=new ArrayList();//初始化容器			
		}else
			throw new Error("index cannot be null or empty");		
	}
	
	//插入元素，块之间有序，块内无序
	public void insert(int value)
	{
		int i=binarySearch(value);
		list[i].add(value);
	}
	
	//二分查找，根据每块的范围确定是第几块
	private int binarySearch(int value)
	{
		int start=0,end=index.length-1,mid=-1;
		while(start<=end)
		{
			mid=start+(end-start)/2;
			if(index[mid]>value)
				end=mid-1;
			else //如果相等，也插入后面
				start=mid+1;
		}
		return start;
	}
	
	//查找元素
	public boolean search(int data)
	{
		int i=binarySearch(data);	//二分法确定第几块
		for(int j=0;j<list[i].size();j++)
		{
			if(data==(int)list[i].get(j))	//顺序查找确定块内第几个
			{
				System.out.println(String.format("查找元素为第： %d块 第%d个 元素", i+1,j+1));
				return true;
			}
		}
		return false;
	}
	
	//打印每块元素
	public void printAll()
	{
		for(int i=0;i<list.length;i++)
		{
			ArrayList l=list[i];
			System.out.print("ArrayList"+i+": ");
			
			for(int j=0;j<l.size();j++)
				System.out.print(l.get(j)+" ");
		}
	}
	
	public static void main (String[] args)
	{
		// TODO Auto-generated method stub
		int[] index= {10,20,30};
		BlockSearch blocksearch=new BlockSearch(index);
		blocksearch.insert(3);
		blocksearch.insert(12);
		blocksearch.insert(29);
		
		blocksearch.insert(9);
		blocksearch.insert(18);
		blocksearch.insert(23);

		blocksearch.insert(5);
		blocksearch.insert(15);
		blocksearch.insert(27);
		
		blocksearch.printAll();

		System.out.println(blocksearch.search(18));
		System.out.println(blocksearch.search(29));		
	}	
	
	
}