1.二分查找

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

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

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

  二分查找大大降低了比較次數(shù)，二分查找的時間復(fù)雜度為：，即。

示例代碼：

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.二叉查找樹

   一般情況下二分查找比順序查找在時間上要快很多，但是在頻繁修改的表中采用二分查找，其效率是非常低下的，因?yàn)轫樞虮淼男薷牟僮餍实拖?，而二分查找的高效就是利用順序表的索引來取值進(jìn)行比較的。為了支持頻繁的修改，我們需要采用鏈表這種數(shù)據(jù)結(jié)構(gòu)。然而，單鏈表的查找效率又非常低，為了解決這一問題，二叉查找樹(BST)便誕生了。

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

   我們將二叉查找樹投影到平面上，實(shí)際上就是有順序的線性表，如下圖所示：

  二叉查找樹既有快速查找的特點(diǎn)，又有快速插入的特點(diǎn)。其查找代碼幾乎和二分查找一樣。

  其時間復(fù)雜度最好情況為，最差情況為。

  最好情況為平衡二叉樹(即每次查找會分成兩半)時，如圖：

   最差情況為所有數(shù)據(jù)全部在一端時(鏈表無索引，需要一個一個搜索),如圖：