經(jīng)典搜索算法之二分查找與二叉查找樹

liang1234_ 2019-07-02

展開全文

1.二分查找

二分查找也稱為折半查找，它是一種效率較高的查找方法。二分查找的使用前提是線性表已經(jīng)按照大小排好了序。這種方法充分利用了元素間的次序關系，采用分治策略。基本原理是：首先在有序的線性表中找到中值，將要查找的目標與中值進行比較，如果目標小于中值，則在前半部分找，如果目標小于中值，則在后半部分找；假設在前半部分找，則再與前半部分的中值相比較，如果小于中值，則在中值的前半部分找，如果大于中值，則在后半部分找。以此類推，直到找到目標為止。

假設我們要在 2，6，11，13，16，17，22，30中查找22，上圖所示，則查找步驟為：

首先找到中值：中值為13（下標：int middle = (0+7)/2），將22與13進行比較，發(fā)現(xiàn)22比13大，則在13的后半部分找；
在后半部分 16，17，22，30中查找22，首先找到中值，中值為17（下標：int middle=(0+3)/2），將22與17進行比較，發(fā)現(xiàn)22比17大，則繼續(xù)在17的后半部分查找；
在17的后半部分 22，30查找22，首先找到中值，中值為22（下標：int middle=(0+1)/2），將22與22進行比較，查找到結(jié)果。

二分查找大大降低了比較次數(shù)，二分查找的時間復雜度為： $O(log{_2}n)$ ，即 log{n} 。

示例代碼：

public class BinarySearch {
	public static void main(String[] args) {
		int arr[] = {2, 6, 11, 13, 16, 17, 22, 30};
		System.out.println("非遞歸結(jié)果,22的位置為:" + binarySearch(arr, 22));
		System.out.println("遞歸結(jié)果,22的位置為:" + binarySearch(arr, 22, 0, 7));
	}
	 //非遞歸
	static int binarySearch(int[] arr, int res) {
	    int low = 0;   
	    int high = arr.length-1;   
	    while(low <= high) {
	    	int middle = (low + high)/2;
	    	if(res == arr[middle]) {
	    		return middle;   
	        }else if(res <arr[middle]) {   
	            high = middle - 1;   
	        }else {   
	            low = middle + 1;   
	        }
	    }
	    return -1;  
	 }
	 //遞歸 
	static int binarySearch(int[] arr,int res,int low,int high){    
	    if(res < arr[low] || res > arr[high] || low > high){
	    	return -1;
	    }
	    int middle = (low+high)/2;
	    if(res < arr[middle]){    
	        return binarySearch(arr, res, low, middle-1);    
	    }else if(res > arr[middle]){    
	        return binarySearch(arr, res, middle+1, high);    
	    }else {    
	        return middle;    
	    }    
	  } 
}

2.二叉查找樹

一般情況下二分查找比順序查找在時間上要快很多，但是在頻繁修改的表中采用二分查找，其效率是非常低下的，因為順序表的修改操作效率低下，而二分查找的高效就是利用順序表的索引來取值進行比較的。為了支持頻繁的修改，我們需要采用鏈表這種數(shù)據(jù)結(jié)構。然而，單鏈表的查找效率又非常低，為了解決這一問題，二叉查找樹(BST)便誕生了。

二叉查找樹的特點是：任一結(jié)點的值都大于其左子樹，小于其右子數(shù)，如下圖所示：