06.分块查找元素

归并排序

1.基本思想
2.排序过程
3.代码实现
4.如何优化
5.复杂度
6.使用场景

1.基本思想

分块查找
- 顾名思义，要先将所有元素按大小进行分块，然后在块内进行查找。在分块时，块内的元素不一定是有序的，只要一个块内的元素在同一区间就行。
- 用较标准的语言描述是：算法的思想是将n个数据元素"按块有序"划分为m块（m≤n）。每一块中的结点不必有序，但块与块之间必须"按块有序"，每个块内的的最大元素小于下一块所有元素的任意一个值。
所以，在使用分块查找时，分成了两步：
- 1>找到元素可能在的块。
- 2>在对应的块内查找元素。

2.排序过程

在上个章节说到，该方法要先分块，那么块应该具有怎样的属性呢？至少要有以下元素：
1>长度
- 一般是固定的长度。
2>起始位置
- 当块的长度固定后，需要确定起始位置才能固定不同的块表示的元素的位置范围。
3>块标识
- 该标识用来标识块内元素的范围，可以用最大值、最小值、平均值等多种方式来表示。

3.代码实现

代码如下所示

public class Block {
	/*block的索引，用来标识块中元素*/
    public int index;
    /*该block的开始位置*/
    public int start; 
    /*块元素长度，在该例子中0代表空元素，不计入block长度*/
    public int length;
	
    public Block(int index, int start, int length) {
        this.index = index;
        this.start = start;
        this.length = length;
    }
}

在该例子中，定义元素数组和块数组，示例如下：

/*主表*/
static int[] valueList = new int[]{
	104, 101, 103, 105,102, 0, 0, 0, 0, 0,
    201, 202, 204, 203,0,   0, 0, 0, 0, 0,
    303, 301, 302,  0,   0,   0, 0, 0, 0, 0
};

/*索引表*/
static Block[] indexList = new Block[]{
	new Block(1, 0, 5),
	new Block(2, 10, 4),
	new Block(3, 20, 3)
};

valueList中的0，可以简单理解为块内的空元素；indexList中的1,2,3代表块内元素的取值范围，第一个块内是100-200之间的元素，第2个块内是200-300之间的元素，以此类推。

在进行元素查找时，先判断是否存在元素可能存在的块。示例如下：

/*确定插入到哪个块中，在该例子中，第一个block中放的是100-200之间的数，第二个block中放的是200-300之间的数，以此类推*/
int index = key/100;
/*找到对应的block*/
for(int i = 0;i < indexList.length; i++) {
   if(indexList[i].index == index) {
       indexItem = indexList[i];
       break;
   }
}

/*如果数组中不存在对应的块，则返回-1，查找失败*/
if(indexItem == null)
   return -1;

找到内对的块后，就在该块内进行搜索，示例代码如下：

如果需要在数组中插入元素，同样需要需要先查找是否存在对应的块，如果存在，则追加到该块中元素的尾部。

   /*在对应的block中查找*/
   for(int i = indexItem.start; i < indexItem.start + indexItem.length; i++) {
       if(valueList[i] == key)
           return i;
    }
   	return -1;
}

完整示例代码如下：

public class Test {
	
	public static class Block {
		/*block的索引，用来标识块中元素*/
	    public int index;
	    /*该block的开始位置*/
	    public int start; 
	    /*块元素长度，在该例子中0代表空元素，不计入block长度*/
	    public int length;
		
	    public Block(int index, int start, int length) {
	        this.index = index;
	        this.start = start;
	        this.length = length;
	    }
	}
	
	/*主表*/
    static int[] valueList = new int[]{
    	104, 101, 103, 105,102, 0, 0, 0, 0, 0,
        201, 202, 204, 203,0,   0, 0, 0, 0, 0,
        303, 301, 302,  0,   0,   0, 0, 0, 0, 0
    };

    /*索引表*/
    static Block[] indexList = new Block[]{
    	new Block(1, 0, 5),
    	new Block(2, 10, 4),
    	new Block(3, 20, 3)
    };
	
	public static void main(String[] args) {
		System.out.println("原始主表：");
		printElemts(valueList);
		
		/*分块查找*/
		int searchValue = 203;
		System.out.println("元素"+searchValue+"，在列表中的索引为："+blockSearch(searchValue)+"\n");
		
	    /*插入数据并查找*/
		int insertValue = 106;
		         
		/*插入成功，查找插入位置*/
	    if (insertBlock(insertValue)) {
		   System.out.println("插入元素"+insertValue+"后的主表：");
		   printElemts(valueList);
		   System.out.println("元素" + insertValue + "在列表中的索引为：" + blockSearch(insertValue));
	    }
	}
	
	public static void printElemts(int[] array) {
	    for(int i = 0; i < array.length; i++){
	        System.out.print(array[i]+" ");
	        if ((i+1)%10 == 0) {
	            System.out.println();
	        }
	    }
	}
	 
	 
	/*插入数据*/
	public static boolean insertBlock(int key) {
	    Block item = null;

	    /*确定插入到哪个块中，在该例子中，第一个block中放的是100-200之间的数，第二个block中放的是200-300之间的数，以此类推*/
	    int index = key/100;
	    int i = 0;
	    /*找到对应的block*/
	    for (i = 0; i < indexList.length; i++) {
	        if (indexList[i].index == index) {
	            item = indexList[i];
	            break;
	        }
	    }
	    /*如果数组中不存在对应的块，则不能插入该数据*/
	    if (item == null) {
	       return false;
	    }

	    /*将元素插入到每个块的最后*/
	    valueList[item.start + item.length] = key;
	    /*更新该块的长度*/
	    indexList[i].length++;
	    return true;
	} 
	 
	public static int blockSearch(int key) {
	    Block indexItem = null;

	    /*确定插入到哪个块中，在该例子中，第一个block中放的是100-200之间的数，第二个block中放的是200-300之间的数，以此类推*/
	    int index = key/100;
	    /*找到对应的block*/
	    for(int i = 0;i < indexList.length; i++) {
	       if(indexList[i].index == index) {
	           indexItem = indexList[i];
	           break;
	       }
	   }

	    /*如果数组中不存在对应的块，则返回-1，查找失败*/
	   if(indexItem == null)
	       return -1;

	   /*在对应的block中查找*/
	   for(int i = indexItem.start; i < indexItem.start + indexItem.length; i++) {
	       if(valueList[i] == key)
	           return i;
	    }
	   	return -1;
	}
    
}

测试结果如下：

原始主表：
104 101 103 105 102 0 0 0 0 0 
201 202 204 203 0 0 0 0 0 0 
303 301 302 0 0 0 0 0 0 0 
元素203，在列表中的索引为：13

插入元素106后的主表：
104 101 103 105 102 106 0 0 0 0 
201 202 204 203 0 0 0 0 0 0 
303 301 302 0 0 0 0 0 0 0 
元素106在列表中的索引为：5