二分查找

二分查找法

将被查找的鍵和子數組的中間鍵比較。如果被查找的鍵小于中間鍵，就在左子數組中繼續查找，如果大于就在右子數組中繼續查找，否則中間鍵就是我們要找的鍵。

思路分析

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