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

思路分析

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;
		}
		
		
		
	}

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