算法之搜索(Java版)-持续更新补充
一、顺序查找
顺序查找对序列本身没有要求（比如不需要是已经排序好的），也不仅限于数字、字符，也可以用于前缀，对象信息的关键信息的匹配（比如查找指定id的相应信息）。
衡量查找性能的一个指标是————ASL(Average Search Length)，ASL=Pi乘Ci，Pi是查找第i个元素的概率，Ci是找到第i个已经比较过次数。
哨兵方式的顺序查找相比较基础的顺序查找在循环的比较部分减少了一般。
//1. 顺序查找
public class SequentialSearch {
private int[] array;
public SequentialSearch(int[] array) {
this.array = array;
}
public int search(int key) {
for(int i = 0; i < array.length; i++) {
if(array[i] == key) {
return i;
}
}
return -1;
}
}
//2. 哨兵方式顺序查找
public class Search2 {
private int[] array;
public Search2(int[] array) {
this.array = array;
}
public int search(int key) {
if(key == array[0]) {
return 0;
}
int temp = array[0];
array[0] = key;
int index = array.length-1;
while(array[index] != key) {
index--;
}
array[0] = temp;
if(index == 0) {
return -1;
}else {
return index;
}
}
}
二、二分查找
如果是顺序查找，7个数最多可能会比较7次，但用二分查找，最多只要3次就能OK。时间复杂度是O（logn）(底数为2)。
二分查找的优化————插值查找
如果数据范围是1~100000,让你找10,那么就不一定要从中间找起了。可以三分之一，四分之一处查找，比如1~10，待查为3，那可以从前面三分之一为划分点。对于要查找的位置有个精确的计算公式P=low+（key-a[low])/(a[high]-a[low])*(high-low)
//1. 二分查找递归与非递归的实现
public class BinarySearch {
private int[] array;
public BinarySearch(int[] array) {
this.array = array;
}
public int searchRecursion(int target) {
if(array == null) {
return -1;
}
return searchRecursion(target, 0, array.length - 1);
}
public int search(int target) {
if(array == null) {
return -1;
}
int start = 0;
int end = array.length - 1;
while(start <= end) {
int mid = start + (end - start) / 2;
if(array[mid] == target) {
return mid;
}else if(target < array[mid]) {
end = mid - 1;
}else {
start = mid + 1;
}
}
return -1;
}
private int searchRecursion(int target, int start, int end) {
if(start > end) {
return -1;
}
int mid = start + (end - start) / 2;
if(array[mid] == target) {
return mid;
}else if(array[mid] < target) {
return searchRecursion(target, mid + 1, end);
}else {
return searchRecursion(target, start, mid -1);
}
}
}
//2. 二分插入排序
public class BinaryInsertSort {
private int[] array;
public BinaryInsertSort(int[] array) {
this.array = array;
}
public void sort() {
int length = array.length;
for(int i = 1; i < length; i++) {
int temp = array[i];
int insertIndex = binarySearch(i - 1, temp);
if(insertIndex != i) {
for(int j = i; j > insertIndex; j--) {
array[j] = array[j - 1];
}
array[insertIndex] = temp;
}
}
}
public void print() {
for(int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
private int binarySearch(int end, int target) {
int start = 0;
int mid = -1;
while(start <= end) {
mid = start + (end - start) / 2;
if(array[mid] > target) {
end = mid - 1;
}else {
//如果相等，也插入到后面
start = mid + 1;
}
}
return start;
}
}三、杨氏矩阵的的查找
杨氏矩阵就是行列递增的矩阵。
杨氏矩阵的操作
- 插入。插入一个数，需要移动其他元素
- 删除。给定x,y坐标，删除那个数，伴随其他元素移动，怎样移动操作最少？
- 查找t是否存在于矩阵中。这也是这篇博客里所要关注的。
- 返回第k大的数。涉及到堆查找，后续博客再细说。
关于查找t是否存在于矩阵，书中给了几种实现的方法：
- 递归实现和非递归实现
优化： - 每次不都从每行的第一个数开始查找，左右上下进行比较然后查找。
- 分治法。杨氏矩阵行列是递增的，那么对角线也是递增的，可以利用对角线划分的区域来缩小要查找数的范围。（实现略）
- 定位查找法。先定位到第一行最右的数，然后只需要往下走，往左走两种操作即可，相比方法2省掉了往右走。
public class YoungSearch {
private int[][] array;
public YoungSearch(int[][] array) {
this.array = array;
}
//1.递归实现
public boolean recursionSearch(int x, int y, int target) {
if(x == array.length || y == array[0].length) {
return false;
}
if(target < array[x][y]) {
return false;
}
if(target == array[x][y]) {
System.out.println(String.format("x: %d, y: %d", x, y));
return true;
}
return recursionSearch(x + 1, y, target) || recursionSearch(x, y + 1, target);
}
//非递归实现
public boolean search(int target) {
for(int i = 0; i < array.length; i++) {
for(int j = 0; j < array[0].length && target >= array[i][j]; j++) {
if(target == array[i][j]) {
System.out.println(String.format("x: %d y: %d", i, j));
return true;
}
}
}
return false;
}
//2.简单优化（向左/右/下走）
public boolean search2(int target) {
int width = array[0].length;
int height = array.length;
if(target >= array[0][0]) {
int i = 0;
for(; i < width && target >= array[0][i]; i++) {
if(target == array[0][i]) {
System.out.println(String.format("x: %d, y: %d", 0, i));
return true;
}
}
if(i > width - 1) {
i--;
}
//循环向下查找
for(int j = 1; j < height; j++) {
if(target == array[j][i]) {
System.out.println(String.format("x: %d, y: %d", j, i));
return true;
}else if(target < array[j][i]) {
for(; i >= 0; i--) {
if(target == array[j][i]) {
System.out.println(String.format("x: %d, y: %d", j, i));
return true;
}else if(target > array[j][i]) {
break;
}
}
if(i < 0) {
i++;
}
}else if(target > array[j][i]) {
for(; i < width; i++) {
if(target == array[j][i]){
System.out.println(String.format("x: %d, y: %d", j, i));
return true;
}else if(target < array[j][i]) {
break;
}
}
if(i > width - 1) {
i--;
}
}
}
}
return false;
}
//3.进一步优化（从第一行最右边的数开始，只需要向下和向左两个操作）
public boolean search3(int target) {
int i = 0;
int j = array[0].length - 1;
int temp = array[i][j];
while(true) {
if(target == temp) {
System.out.println(String.format("x: %d, y: %d", i, j));
return true;
}else if(j > 0 && target < temp){
temp = array[i][--j];
}else if(i < array.length - 1 && target > temp) {
temp = array[++i][j];
}else {
return false;
}
}
}
}四、分块查找
对于待查找的数据列表来说，如果元素变动很少，那么可以先进行排序再查找。但如果这个数据经常需要添加元素，那么每次查找前都需要排序，这并不是一个好的选择。
就有了分块查找，这个概念再学数据库的时候听过。分块查找里有索引表和分块这两个概念。索引表就是帮助分块查找的一个分块依据，就是一个数组，用来存储每块最大的存储值（范围上限）；分块就是通过索引表把数据分为几块。
原理：当需要增加一个元素的时候，先根据索引表，获取这个元素应该在那一块，然后直接把元素加入到相应的块里，而块内的元素直接不需要有序。
从上面可知，分块查找只需要索引表有序，每一个块里的元素可以是无序的，但第i块的每个元素一定比第i-1块的每一个元素大（小）。当索引表很大的时候，可以对索引表进行二分查找，锁定块的位置，然后对块内的元素进行顺序查找。总性能不如二分查找，但强过顺序查找，更好的是不需要数列完全有序。
举个例子，比如索引表为【10，20，30】,分块一【2，1，4，2】分块二【19，15，18，】分块三【22，27，23】，现在要增加22这个数，直接根据索引表把22放到分块三最后就行了【22,27,23,22】。
可以看出，分块查找同时有顺序查找和二分查找的有点————不需要有序、速度快。
应用场景
视频网站对用户观看行为记录，每个用户分别观看了一个视频多久，如果对每条这样的记录都放到一个表里，那太多了，可以根据具体业务做分表，一天一个表，表名如t_user_watch_xxx_20180806，存储查询的时候就可以根据时间去做一个表的分块，在查询详细的记录。
//分块查找
import java.util.ArrayList;
public class BlockSearch {
private int[] index;
private ArrayList<ArrayList<Integer>> list;
public BlockSearch(int[] index) {
this.index = index;
list = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < index.length; i++) {
list.add(new ArrayList<Integer>());
}
}
public void insert(Integer value) {
int i = binarySearch(value);
list.get(i).add(value);
}
public boolean search(int data) {
int i = binarySearch(data);
for(int j = 0; j < list.get(i).size(); j++) {
if(data == list.get(i).get(j)) {
return true;
}
}
return false;
}
public void printAll() {
for(int i = 0; i < list.size(); i++) {
ArrayList<Integer> l = list.get(i);
System.out.println("ArrayList: " + i + ":");
for(int j = 0; j < l.size(); j++) {
System.out.println(l.get(j));
}
}
}
private int binarySearch(int target) {
int start = 0;
int end = index.length - 1 ;
int mid = -1;
while(start <= end) {
mid = (start + end) / 2;
if(target == index[mid]) {
return mid;
}else if(target < index[mid]) {
end = mid - 1;
}else {
start = mid + 1;
}
}
return start;
}
}
