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

思路分析

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;
		}
		
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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;
		}
		
		
		
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

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