测试不得不懂的算法_01_二分查找算法
二分查找算法的定义
二分查找算法就是我们通常所说的折半算法。即先找到一组数的中间值,再将目标值与中间值进行比较,如果中间值和目标值一致,则直接返回目标值,如果中间值和目标值不一致,则继续用相同的方法进行中值查找,直至中间值和目标值一致为止;
二分查找算法的适用条件
第一:数据必须有序,即必须按照从大到小或者从小到大的顺序进行排列;
第二:数据内不能出现重复数据,如果出现重复数据,会导致查询出的结果不唯一,进而失去查找意义;
二分查找算法考察的知识点
程序的递归调用
应用举例
现有数组 int nums = {1,3,6,8,11},要求查找出数字 8 所在的索引值。 java 实现如下:
public class MyStudy01 {
public static void main(String[] args) {
int[] nums = {1,3, 6, 8,11};
int target = 8;
int searchKey = searchIndex( nums, 0, nums.length - 1, target );
System.out.println( "此时所查找的值的索引为:" + searchKey );
}
/**
* @Description: TODO 二分查找的方法
* @Param:num:待查找的数组、startIndex:起始坐标、endIndex“截止坐标、target:目标值
* @return: 返回查询出的索引
* @Author: haibao.wang
* @date: 2019/12/17
*/
public static int searchIndex(int[] num, int startIndex, int endIndex, int target) {
//第一步获取中值的索引值:
int middleIndex = (startIndex + endIndex) / 2;
//第二步获取中值索引对应的值
int middleValue = num[middleIndex];
//第三步 开始判断
//如果中值等于目标查找的值,则直接返回此时的索引,如果不等于则重新进行递归
if (middleValue == target) {
return middleIndex;
} else if (target < middleValue) {
return searchIndex( num, 0, middleIndex, target );
} else {
return searchIndex( num, middleIndex, num.length, target );
}
}
}
此时程序的运行结果为 3;