查找（上：线性、二分）
1. 线性查找
1.1 基本介绍
一种简单的查找方式，从头到尾遍历，直到找到指定数字。
1.2 设计思路
for/while循环遍历数组，找到指定数字则返回下标，否则返回-1。
1.3 代码实现
public class Demo24 {
public static void main(String[] args) {
int[] arr = {1, 8, 10, 89, 1000, 1234};
int num = 81;
if (seqSearch(arr, num) == -1) {
System.out.println("未找到");
} else {
System.out.println(seqSearch(arr, num));
}
}
/**
* 线性查找
* @param arr 数组
* @param value 目标值
* @return 下标
*/
public static int seqSearch(int[] arr, int value) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == value) {
return i;
}
}
return -1;
}
}
2. 二分查找
2.1 基本介绍
二分查找又称折半查找，即从中间数开始找，然后根据比较结果选择需要折半的一边出发，然后再次折半，以此类推找出元素。
注意：二分法需要数据首先有序
2.2 设计思路-单数版
- 确定当前数组的下标 mid = (left + right)/2;
- 让需要查找的数 findVal 和 arr[mid] 比较
(1) findVal > arr[mid] 说明要查找的数在 mid 右边，因此向右递归查找
(2) findVal < arr[mid] 说明要查找的数在 mid 左边，因此向左递归查找
(3) findVal = arr[mid] 说明找到，返回下标
2.3 代码实现
public class Demo25 {
public static void main(String[] args) {
int[] arr = {1, 8, 10, 89, 99, 100, 111, 112, 113, 115, 1000,
1000, 1000, 1000, 1000, 1234};
ArrayList<Integer> findIndex = new ArrayList<>();
int findVal = 0;
System.out.println(binarySearch(arr, 0, arr.length - 1, findVal));
}
/**
* 单个数据查找
* @param arr 数组
* @param left 左下标
* @param right 右下标
* @param findVal 目标值
* @return 下标
*/
public static int binarySearch(int[] arr, int left, int right, int findVal) {
// 判断递归结束的临界条件
if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
return -1;
}
// 取中间值
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal == midVal) {
return mid;
}
return findVal > midVal ? binarySearch(arr, mid + 1, right, findVal)
: binarySearch(arr, left, mid - 1, findVal);
}
}
可以发现，上述代码只能寻找到单个符合条件的目标值，局限性大，因此对代码做个调整
2.4 设计思路
- 找到第一个匹配的索引值
mid的时候，不要马上返回；- 向
mid索引值的左边扫描，将所有与findVal相等的元素的下标加入到返回集合中；- 向
mid索引值的右边扫描，将所有与findVal相等的元素的下标加入到返回集合中；- 整体返回。
2.5 代码实现
public class Demo25 {
public static void main(String[] args) {
int[] arr = {1, 8, 10, 89, 99, 100, 111, 112, 113, 115, 1000,
1000, 1000, 1000, 1000, 1234};
ArrayList<Integer> findIndex = new ArrayList<>();
int findVal = 0;
System.out.println(binarySearch2(arr, 0, arr.length - 1, findVal));
System.out.println(binarySearch3(findIndex, arr, 0, arr.length - 1, findVal));
}
/**
* 找所有符合的目标值下标
* @param arr 数组
* @param left 左下标
* @param right 右下标
* @param findVal 目标值
* @return 目标值下标集合
*/
public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
// 当 left > right 时候，说明已经递归完毕，仍没有找到
if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
return new ArrayList<>();
}
// 折半，取值
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal == midVal) {
final ArrayList<Integer> list = new ArrayList<>();
list.add(mid);
int index = mid - 1;
// 向左找，注意临界条件
while (index >= 0 && arr[index] == midVal) {
list.add(index--);
}
index = mid + 1;
// 向右找
while (index <= right && arr[index] == midVal) {
list.add(index++);
}
return list;
}
return findVal > midVal ? binarySearch2(arr, mid + 1, right, findVal)
: binarySearch2(arr, left, mid - 1, findVal);
}
/**
* 递归法
*/
public static List<Integer> binarySearch3(List<Integer> findIndex, int[] arr, int left, int right, int findVal) {
// 当 left > right 时候，说明已经递归完毕，仍没有找到
if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
return new ArrayList<>();
}
// 折半，取值
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal == midVal) {
findIndex.add(mid);
binarySearch3(findIndex, arr, left, mid - 1, findVal);
binarySearch3(findIndex, arr, mid + 1, right, findVal);
return findIndex;
}
return findVal > midVal ? binarySearch3(findIndex, arr, mid + 1, right, findVal)
: binarySearch3(findIndex, arr, left, mid - 1, findVal);
}
}
| 上一篇 | 总目录 | 下一篇 |
|---|---|---|
| 七、排序（下：归并、基数） | 数据结构篇（Java）目录 | 未完待续 |