经典搜索算法的二进制搜索和二进制搜索树

二进制搜索也称为半搜索，这是一种更有效的搜索方法. 使用二进制搜索的前提是线性表已根据大小进行了排序. 该方法充分利用了元素之间的顺序关系，并采用了分而治之的策略. 基本原理是: 首先在有序线性表中找到中位数，将要找到的目标与中位数进行比较，如果目标小于中位数，则在上半部分中找到，如果目标小于中位数，然后在下半年找到;假设在上半年找到它，则将其与上半年的中位数进行比较. 如果小于中位数，则会在中位数的前半部分找到它. 如果大于中位数，则在下半部分找到. 依此类推，直到找到目标为止.

假设我们要在2、6、11、13、16、17、22、30中找到22，如上图所示，搜索步骤为:

首先找到中位数: 中位数为13（下标: int middle =（0 + 7）/ 2）. 比较22到13，发现22大于13，然后在13的下半部分查找它；在16、17、22、30的后半部分中查找22，首先找到中位数，中位数为17（下标: int middle =（0 + 3）/ 2），将22与17进行比较，找到22的比率17大，在17下半年继续搜索；在17 22的后半部分中，搜索30为22，首先找到中位数，中位数为22（下标: int middle =（0 + 1）/ 2），将22与22进行比较以找到结果.

二进制搜索大大减少了比较次数. 二进制搜索的时间复杂度是:

那是

.

示例代码:

public class BinarySearch {
	public static void main(String[] args) {
		int arr[] = {2, 6, 11, 13, 16, 17, 22, 30};
		System.out.println("非递归结果,22的位置为:" + binarySearch(arr, 22));
		System.out.println("递归结果,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;    
	    }    
	  } 
}

通常，二进制搜索比顺序搜索要快得多，但是在频繁修改的表中使用二进制搜索，其效率非常低，因为顺序表的修改操作效率低下，并且二进制搜索效率很高. 序列表的索引以比较这些值. 为了支持频繁的更改，我们需要使用链表数据结构. 但是，单链接列表的搜索效率非常低. 为了解决这个问题，诞生了二进制搜索树（BST）.

二分查找树的特征是任何节点的值都大于其左子树而小于其右子号，如下图所示:

我们将二叉搜索树投影到平面上二叉排序树算法，该平面实际上是一个有序的线性表，如下所示:

二进制搜索树具有快速搜索和快速插入的特征. 搜索代码与二进制搜索几乎相同.

最佳时间复杂度是:

，最坏的情况是

.

最好的情况是平衡二叉树时（即，每次搜索将分为两半），如图所示:

最坏的情况是所有数据都在一端（链接列表没有索引，您需要一个一个地搜索）二叉排序树算法，如图所示:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-253377-1.html