2
1
0
1. 云栖社区>
2. 博客>
3. 正文

## 算法之搜索(Java版)-持续更新补充

kissjz 2018-08-06 21:12:44 浏览1773

# 一、顺序查找

//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;
}
}
}


# 二、二分查找

## 二分查找的优化————插值查找

//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;
}
}

# 三、杨氏矩阵的的查找

## 杨氏矩阵的操作

1. 插入。插入一个数，需要移动其他元素
2. 删除。给定x,y坐标，删除那个数，伴随其他元素移动，怎样移动操作最少？
3. 查找t是否存在于矩阵中。这也是这篇博客里所要关注的。
4. 返回第k大的数。涉及到堆查找，后续博客再细说。

1. 递归实现和非递归实现
优化：
2. 每次不都从每行的第一个数开始查找，左右上下进行比较然后查找。
3. 分治法。杨氏矩阵行列是递增的，那么对角线也是递增的，可以利用对角线划分的区域来缩小要查找数的范围。（实现略）
4. 定位查找法。先定位到第一行最右的数，然后只需要往下走，往左走两种操作即可，相比方法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;
}
}
}
}

# 四、分块查找

### 应用场景

//分块查找
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++) {
}
}

public void insert(Integer value) {
int i = binarySearch(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;
}
}


kissjz
+ 关注