二分法查找及其變形 Java 實作（推薦）

描述：

給定一個數組

arr

，和需要查找的數

value

。

文章目錄

• 1. 資料有序且無重複，查找給定值
• 2. 資料有序且有重複，查找第 1 個給定的值
• 3. 資料有序且有重複，查找最後一個值等于給定值的元素
• 4. 資料有序且有重複，查找第一個大于等于給定值的元素
• 5. 資料有序且有重複，查找最後一個小于等于給定值的元素

1. 資料有序且無重複，查找給定值

前提條件：

1.數組為升序排列

2.不存在重複的資料

算法時間複雜度：

當 n/2k = 1 時, k 是總共縮小的次數,而每一次縮小操作隻涉及兩個資料的大小比較,經過 k 次區間縮小的操作,時間複雜度就是O(k),n/2k = 1得到 k=log2 n ,故時間複雜度就是 O(logn)。

算法核心思想：

• 定義兩個變量， low = 0, high = arr.length - 1,則 mid=low+(high - low)/2。
• 如果 value == arr[mid]，中間值正好等于要查找的值，則傳回下标，return mid;
• 如果 value < arr[mid]，要找的值小于中間的值，則再往數組的小端找，high=mid-1;
• 如果 value > arr[mid]，要找的值大于中間的值，則再往數組的大端找，low=mid+1;

代碼實作：

class Solution{
	public int binarySearch(int[] arr,int value) {
		int low = 0;
		int high = arr.length-1;
		while(low<=high) {
		// low+(high-low)/2，由于計算機的位運算比除法快,故可改成 low+((high-low)>>1)
			int mid = low+((high-low)>>1);
			if(value == arr[mid]) {
				return mid;
			}else if(value > arr[mid]) {
				low = mid+1;	
			}else{
			//value < arr[mid]
				high = mid-1;
			}
		}
		return -1;//沒有找到傳回-1
	}
}
           

2. 資料有序且有重複，查找第 1 個給定的值

代碼實作：

class Solution{
	public int binarySearch(int[] arr,int value) {
		int low = 0;
		int high = arr.length-1;
		while(low<=high) {
		// low+(high-low)/2，由于計算機的位運算比除法快,故可改成 low+((high-low)>>1)
			int mid = low+((high-low)>>1);
			if(value == arr[mid]) {
			// 因為要找第一個出現的元素 value，若找到的元素與 value 值相同但不是第一個出現的元素，則視其為比 value 大的元素，繼續縮小搜尋區間，即将 high = mid -1 繼續查找。
				// arr[mid-1] != value ，表示找到了第一個出現的 value。
				if(mid == 0 || arr[mid-1] != value){
					return mid;
				}else{
					high = mid - 1; 
				}
			}else if(value > arr[mid]) {
				low = mid+1;	
			}else{
			//value < arr[mid]
				high = mid-1;
			}
		}
		return -1;//沒有找到傳回-1
	}
}
           

3. 資料有序且有重複，查找最後一個值等于給定值的元素

代碼實作：

class Solution{
	public int binarySearch(int[] arr,int value) {
		int low = 0;
		int high = arr.length-1;
		while(low<=high) {
		// low+(high-low)/2，由于計算機的位運算比除法快,故可改成 low+((high-low)>>1)
			int mid = low+((high-low)>>1);
			if(value == arr[mid]) {
			// 因為要找最後一個出現的元素 value，若找到的元素與 value 值相同但不是最後一個出現的元素，則視其為比 value 小的元素，繼續縮小搜尋區間，即将 low = mid+1 繼續查找。
				// arr[mid+1] != value ，表示找到了第一個出現的 value。
				if(mid == n-1 || arr[mid+1] != value){
					return mid;
				}else{
					low = mid + 1; 
				}
			}else if(value > arr[mid]) {
				low = mid+1;	
			}else{
			//value < arr[mid]
				high = mid-1;
			}
		}
		return -1;//沒有找到傳回-1
	}
}
           

4. 資料有序且有重複，查找第一個大于等于給定值的元素

代碼實作：

class Solution{
	public int binarySearch(int[] arr,int value) {
		int low = 0;
		int high = arr.length-1;
		while(low<=high) {
		// low+(high-low)/2，由于計算機的位運算比除法快,故可改成 low+((high-low)>>1)
			int mid = low+((high-low)>>1);
			// 這裡已經不是要找一個與給定值相等元素，而是不等于的關系，是以要轉換判定條件。
			if(arr[mid] >= value) {
				// 找到一個大于等于給定值的元素,還要繼續判定是否是第一個。
				if(mid == 0 || arr[mid-1] < value){
					return mid;
				}else{
					high = mid - 1; 
				}
			}else{
			//arr[mid] < value 
				low = mid+1;
			}
		}
		return -1;//沒有找到傳回-1
	}
}
           

5. 資料有序且有重複，查找最後一個小于等于給定值的元素

代碼實作：

class Solution{
	public int binarySearch(int[] arr,int value) {
		int low = 0;
		int high = arr.length-1;
		while(low<=high) {
		// low+(high-low)/2，由于計算機的位運算比除法快,故可改成 low+((high-low)>>1)
			int mid = low+((high-low)>>1);
			 // 這裡已經不是要找一個與給定值相等元素，而是不等于的關系，是以要轉換判定條件。
			if(arr[mid] <= value) {
				// 找到一個小于等于給定值的元素,還要繼續判定是否是最後一個。
				if(mid == n-1 || arr[mid+1] > value){
					return mid;
				}else{
					low = mid+1; 
				}
			}else{
			//arr[mid] > value 
				high = mid-1;
			}
		}
		return -1;//沒有找到傳回-1
	}
}
           

參考連結：算法–二分查找–查找給定條件的值 https://blog.csdn.net/qq_21201267/article/details/89339488