写一个简单的二分查找
程序员文章站
2022-07-12 09:35:00
...
二分查找的概念: 二分查找是算法里面比较简单的算法,很多人接触算法都是从二分查找开始入门的, 二分查找也叫折半查找, 它是运用分治策略的典型例子。折半查找方法适用于不经常变动而查找频繁的有序列表。 所以它在有序数组中经常被使用到。
经过分析,总结出二分查找的编写需要注意的几个点。
1. 计算出最低的索引:0
2. 计算出最高的索引:length -1
3. 计算出中位数的索引: (最高 + 最低) / 2
4. 如果要查找的数大于中位数:则把最低位的索引改变成 中位数的索引 + 1
5. 如果要查找的数小于中位数: 则把最高位的索引改变成 中位数的索引 - 1
6. 如果要查找的数刚好等于中位数: 则直接break
7. 如果低位大于了高位,则证明没有找到需要找到的数
下面就为最简单的二分查找提供一个代码实例:注意给到的数组必须是有顺序的,不能是乱序的
/*
这是一个二分超找的简单实例
二分查找的概念:
二分查找是算法里面比较简单的算法,很多人接触算法都是从二分查找开始入门的,
二分查找也叫折半查找,
它是运用分治策略的典型例子。折半查找方法适用于不经常变动而查找频繁的有序列表。
所以它在有序数组中经常被使用到。
*/
public class TwoSearch {
public static void main(String[] args) {
// 随便去指定一个数组
int[] number = {1,2,3,11,22,33,44,55,66,77};
//随便指定一个需要查找的数据
int findValue = 3;
// 计算最低位的索引
int low = 0;
// 计算最高位的索引
int high = number.length - 1;
// 计算中位的索引
int mid = (low + high) / 2;
System.out.println((low + high) / 2);
// 先对需要查找的值是否在范围里面进行判断
if (findValue > number[high] || findValue < number[low]){
System.out.println("所需要查找的值不存在");
return;
}
while (low <= high){
// 首先判断要找的值是否等于中位数,如果刚好等于就直接break
if (number[mid] == findValue){
System.out.println("找到了值,下标是" + mid);
break;
}
//大于中位数的情况,对最低的索引进行初里,中位数索引+1
if(findValue > number[mid]){
low = mid + 1;
mid = (low + high) / 2;
continue;
}
//小于中位数的情况,对最高的索引进行初里,中位数索引-1
if (findValue < number[mid]){
high = mid - 1;
mid = (high + low)/ 2;
}
}
}
}
上一篇: 顺时针打印矩阵
下一篇: 完全背包问题 :背包dp