查找算法之一：二分查找（递归实现）

二分查找的递归实现

思路分析

1、确定该序列的中间的下标mid：

mid = （left + right）/2；

2、让需要查找的数findVal 与 arr[mid]进行比较：

（1）findVal > midVal，则进行向右递归，查找findVal；

递归的边界条件是：mid+1，right

（2）findVal < midVal，则进行向左递归，查找findVal；

递归的边界条件是：left，mid-1

（3）findVal == midVal，则表明找到了待查找的findVal，

直接return mid的坐标值；

3、什么时候结束递归？

（1）找到就结束递归，直接return mid；

（2）递归查找完整个数组，仍然没有找到findVal，也需要结束递归，

此时，left > right。

4、对于二分查找的功能的完善，

即：当待查找的findVal在序列中出现多次时，可以返回所有的出现位置的索引值

== >通过集合来实现该功能：

（1）当找到findVal时，即midVal == findVal时，

定义一个ArrayList int temp =mid;//暂存mid，用于向mid的前后遍历

然后从mid到的索引，先开始向前遍历：

while(–temp>=0 && arr[temp] == findVal)

接着从mid到的索引，先开始向后遍历：

while(++temp <= arr.length-1 && arr[temp] == findVal)

=>即：保证数下标不越界的同时，又找到了== findVal的元素 直到两个while循环结束，return 这个ArrayList即可；

（2）如果出现left > right，表明找不到==findVal的值，直接return一个空的ArrayList即可

代码实现

1、基础的二分查找

【对于findVal只要查找到序列中一个与它相等，就立即返回对应的下标值】

public static int binarySearch(int[] arr,int left,int right,int findVal) {//递归的终止条件之二：找不到该元素if(left > right) {return -1;}//没有查找完该序列的时候int mid = (left + right)/2;int midVal = arr[mid];//System.out.println("二分查找");//判断midVal与findVal的大小关系if(findVal > midVal) {//（1）findVal > midVal，则进行向右递归，查找findVal；return binarySearch(arr, mid+1, right, findVal);}else if(findVal < midVal) {return binarySearch(arr, left, mid-1, findVal);//（2）findVal < midVal，则进行向左递归，查找findVal；}else {//（3）findVal == midVal，则表明找到了待查找的findVal，直接return mid的坐标值；return mid;}}

2、对于二分查找的功能的完善，

即：当待查找的findVal在序列中出现多次时，可以返回所有的出现位置的索引值

public static List<Integer> binarySearch(int[] arr,int left,int right,int findVal) {//找不到findVal---->递归的终止条件之二if(left > right) {return new ArrayList<Integer>();}//还没有递归结束的时候int mid = (left+right)/2;int midVal = arr[mid];if(findVal > midVal) {//需要向右递归return binarySearch(arr, mid+1, right, findVal);}else if(findVal < midVal) {//需要向左递归return binarySearch(arr, left, mid-1, findVal);}else {List<Integer> list = new ArrayList<>();int temp = mid;//用于向mid的左右查找，是否有==findVal的元素//【因为arr[]是有序的】//向左查找有没有==findVal的元素while(--temp>=0 && arr[temp]==findVal) {list.add(temp);}//将mid加入list中list.add(mid);//向右查找有没有==findVal的元素while(++mid<=arr.length-1 && arr[mid]==findVal) {list.add(mid);}return list;}}

不要只知道因为的学习新知识，适当的时侯回过头看看以前学的东西，会有一种 突然变通透 的感觉！！！！