vlambda博客
学习文章列表

测试不得不懂的算法_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;