二分查找算法(思路分析)

注意: 使用二分查找算法的前提是数组是有序的

思路分析:

1. 首先确定该数组中中间的下标

   • mid = (right - left)/2 + left

2. 然后让需要查找的数findVal和arr[mid]比较

   ①如果findVal > arr[mid],说明你要查找的数在mid的右边,因此需要递归的向右查找

   ②如果findVal < arr[mid],说明你要查找的数在mid的左边,因此需要递归的向左查找

   ③如果findVal == arr[mid],说明找到了目标值,则直接返回mid

   • 但是注意: 这个时候我们使用的是递归来实现的二分查找,那么我们必须要知道在什么时候来结束递归?
     • 我们递归结束的状态有两种:
       1. 找到目标值之后就结束递归
       2. 递归完整个数组之后,如果任然没有找到findVal(目标值),也就需要结束递归
          • 也就是当left > right的时候结束递归
   • 什么叫做结束递归?
     • 其实就是不继续递归就是结束递归,如果正常递归的时候会一直重复调用递归的方法,如果在某次的递归调用中执行递归方法的时候没有进入下一次递归调用中,那么这个时候就是结束了递归
       • 也就是结束递归就是不继续进行递归

我们这个时候要考虑: 如果对于一个有序数组中,有多个相同的数值时,我们如果要查找到的目标值对应数组中的多个重复元素,这个时候我们要将数组中的多个索引返回,这个要如何实现?

我们只需要找到一个符合条件的mid之后,进行向左和向右扫描将左边和右边也等于findVal的元素的下标一起放到一个List接口实现类中即可

• 这里的向右和向左扫描其实就是一个遍历,我们用一个临时变量,然后写两个while循环即可解决