查找
在 Java 中我们常用的查找有两种：
- 顺序查找
- 即：有一个数组/数列
{"a", "b", "c", "d"}我们从键盘中输入任意一个 与数组类型相同的值，然后循环遍历这个数组，判断数组中是否有这个值，如果有就返回其所在的索引值 - 二分查找
- 二分查找有个前提条件，就是这个数组必须是有序的。
- 二分查找即：有一个数组
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}，在查找的时候将数组从中间分成两分，要查找的值如果比 中间值大则往右边的数据查找，否则反之。就这样一直对半分，直到找到这个值。
顺序查找的代码实现
// 顺序查找
// 被查找的数组
String strArray[] = {"a", "b", "小明", "Java"};
// 要查找的值
String findName = "小明";
// 存放查找结果 默认为 -1
int result = -1;
// 循环遍历数组
for (int index = 0; index < strArray.length; index++) {
if (strArray[index].equals(findName)) {
result = index;
break;
}
}
// 如果 result 为 -1 说明没找到
switch (result) {
case -1:
System.out.println(findName + " 在该数组中不存在");
break;
default:
System.out.println(findName + " 在该数组索引为 " + result);
}
二分查找代码实现
思路分析:
- 找到中间数值, 然后用要查找的值 与中间值进行比较,
- 如果中间值 比 要查找的值比小 (数组是从小到大排列) 则 以本次数组的中间索引 +1 为下一次查找的第一个索引值
- 如果中间值 比 要查找的值比大 (数组是从小到大排列) 则 以本次数组的中间索引 -1 为下一次查找的最后一个索引值
- 重复以上操作, 直到 中间值等于寻找的值或中间值等于起始值结束
以下是该思路的图形表示:
有了思路接下来按照思路实现代码:
/*
再次确定思路:
1. 需要 变量记录 最大最小索引值
2. 无限循环把数组对半分, 每次循环需要修改对应的 最小或最大值, 再计算中间值
直到 中间值对应的元素与要查找的元素一致 或
中间值等于最小索引值且中间值对应的元素不等于要查找值,时退出循环
3. 定义变量接收查找结果,
如果找到结果会将索引值赋给这个变量
默认为 -1 如果循环结束后 依旧为 -1
说明 要查找的值在数组中不存在
*/
// 被查找数组
int twoPointsArray[] = {4, 5, 8, 14, 20, 40, 46, 54, 80};
// 定义最小索引值
int startIndex = 0;
// 定义最大索引值
int endIndex = twoPointsArray.length - 1;
// 定义中间值, 要获取中间值,必需先获取最小和最大索引值
int midIndex = (startIndex + endIndex) / 2;
// 要查找的元素
int findItem = 1;
// 定义变量接收查找结果
int findResult = -1;
// 因为无法确定循环次数 所以使用 while 循环
while (true) {
// 如果数组的中间值对应索引的元素与要查找的元素一致,
// 将该索引值返回给 findResult 变量 并终止循环
if (twoPointsArray[midIndex] == findItem) {
findResult = midIndex;
break;
}
// 如果中间值和起始值中止一致,且中间值在数组中对应的元素与要查找的值不一致
// 代表该数组中没有这个值,直接退出循环
else if (startIndex == endIndex) {
break;
}
// 如果数组的中间值对应索引的元素比要查找的元素大,
// 将最大索引值设为 中间值 -1 , 并重新计算中间值
else if (twoPointsArray[midIndex] > findItem) {
endIndex = midIndex - 1;
midIndex = (startIndex + endIndex) / 2;
}
// 上面三种情况处理完 只剩下最后一种就是 中间值对应的元素 小于 要查找的值
// 将最小索引值设为 中间值 +1, 并重新计算中间值
else {
startIndex = midIndex + 1;
midIndex = (startIndex + endIndex) / 2;
}
}
switch (findResult) {
case -1:
System.out.println(findItem + " 在该数组中不存在");
break;
default:
System.out.println(findItem + " 在数组中的索引为: " + findResult);
}
为什么中间值对应的元素 大于或小于 要查找的值时要将 最小或最大索引 -1 或 +1：
因为在我们比对中间值对应的元素是否 大于或小于 要查找的值时，就相当于判定了中间值对应的元素不等于要查找的值，既然不等于 要查找的值，那么后续的查找也可以将这个值排除在外了。
Original: https://www.cnblogs.com/jwyqn/p/16187948.html
Author: 假文艺青年。
Title: Java 顺序查找 二分查找
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/570060/
转载文章受原作者版权保护。转载请注明原作者出处！