二分查找

二分查找法

将被查找的键和子数组的中间键比较。如果被查找的键小于中间键，就在左子数组中继续查找，如果大于就在右子数组中继续查找，否则中间键就是我们要找的键。

思路分析

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

   mid = (left + right) / 2

2. 然后让需要查找的数 findVal 和 arr[mid] 比较
   1. findVal > arr[mid] , 说明你要查找的数在mid 的右边, 因此需要递归的向右查找
   2. findVal < arr[mid], 说明你要查找的数在mid 的左边, 因此需要递归的向左查找
   3. findVal == arr[mid] 说明找到，就返回

• 什么时候我们需要结束递归.

1. 找到就结束递归
2. 递归完整个数组，仍然没有找到findVal ，也需要结束递归 当 left > right 就需要退出

性质

1. 在N个键的有序数组中进行二分查找，最多需要进行（lgN+1）次比较：

   二分查找相对于线性查找，虽然减少了比较次数但无法减少运行所需时间，故：

2. 向大小为N的有序数组插入一个新的元素，在最坏情况下需要访问（ ~ 2N）次数组，因此向一个空符号表中插入N个元素在最坏情况下需要访问（ ~ N^2）次数组。

代码实现

1. 数组元素不重复时：

   public static int binarySearch(int[] arr, int left, int right, int findVal) {
     // 当left > right 时，说明递归整个数组，但是没有找到
     if (left > right) {
     	return -1;
     }
     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 {
     	return mid;
     }
   }
              

2. 数组元素能找到重复值时：

   public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
     // 当left > right 时，说明递归整个数组，但是没有找到
     if (left > right) {
     	return new ArrayList<Integer>();
     }
     int mid = (left + right) / 2;
     int midVal = arr[mid];
     if (findVal > midVal) { // 向右递归
     	return binarySearch2(arr, mid + 1, right, findVal);
     } else if (findVal < midVal) { // 向左递归
     	return binarySearch2(arr, left, mid - 1, findVal);
     } else {
     	// * 思路分析
     	// * 1. 在找到mid 索引值，不要马上返回
     	// * 2. 向mid 索引值的左边扫描，将所有满足1000， 的元素的下标，加入到集合ArrayList
     	// * 3. 向mid 索引值的右边扫描，将所有满足1000， 的元素的下标，加入到集合ArrayList
     	// * 4. 将Arraylist 返回
     	List<Integer> resIndexlist = new ArrayList<Integer>();
           //添加mid进list
           resIndexlist.add(mid); 
     	//向mid 索引值的左边扫描，将所有满足1000， 的元素的下标，加入到集合ArrayList
     	int temp = mid - 1;
     	while(true) {
     		if (temp < 0 || arr[temp] != findVal) {//退出
     			break;
     		}
     		//否则，就temp 放入到resIndexlist
     		resIndexlist.add(temp);
     		temp -= 1; //temp 左移
     	}
     	
     	//向mid 索引值的右边扫描，将所有满足1000， 的元素的下标，加入到集合ArrayList
     	temp = mid + 1;
     	while(true) {
     		if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
     			break;
     		}
     		//否则，就temp 放入到resIndexlist
     		resIndexlist.add(temp);
     		temp += 1; //temp 右移
     	}
     	return resIndexlist;
     }
   }