Java基本查找算法--二分查找

淩亂°似流年 2023-10-06 11:05 137阅读 0赞

## `一、二分法查找` ##

> 又称为折半查找。要求线性表示`有序`表，即表中记录按关键字有序。二分查找的基本思想是:设R\[low…high\]是当前查找区间，首先确定该区间的中点位置 mid =（low+high）/ 2；然后将待查的k值与R\[mid\].key进行比较，若相等则查找成功并返回该位置，否则须返回确定新的查找区间；若R\[mid\].key > k 则由表的有序性可知R\[mid\].key < k,则由表的有序性可知R\[mid…n-1\].key均大于k，因此若表中存在关键字等于k的记录，则该记录必定是在位置mid左边的子表R\[0…mid-1\]中，故新的查找区间是左子表R\[0…mid-1\]；类似的，若R\[mid.key\] < k,则要查找的k必在mid的右子表中R\[mid+1…n-1\]中，即新的查找区间是右子表R\[mid+1…n-1\]。下一次查找是针对新的查找区间进行的。因此，可以从初始的查找区间R\[0…n-1\]开始，每经过一次与当前查找区间的中点位置上的关键字的比较，就可以确定查找是否成功，不成功则当前的查找区间缩小一半。这个过程重复直至找到关键字为k的记录，或者直至当前区间为空为止。

> 示例：在有序数组A = \[14, 15, 16, 17, 18, 19, 19, 20\]中通过二分法查找数字 16 是否存在，并输出结果。

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]

public void binSearch(int[] a, int k) {
        
    	int find =  -1, // 最终查询出来结果的位置
    		low = 0, //开始点
    		high = a.length - 1, // 结束点
    		mid; // 中点
    	while(low <= high) {
        
    		mid =(low + high) / 2;
    		// 如果相等
    		if (a[mid] == k) {
        
    			find = mid;
    			break;
    		}
    		// 不相等
    		if (a[mid] > k) {
        
    			high = mid - 1;
    		} else {
        
    			low = mid + 1;
    		}
    	}
    	// 判断是否查找成功
    	if (find > 0) {
        
    		System.out.println("查找成功，该元素在表中位置为: " + find);
    	} else {
        
    		System.out.println("查找失败！");
    	}
    }

> 算法分析: 二分查找过程可用二叉树来描述，把当前查找区间的中间位置上的记录作为根，左子表和右子表中的记录分别作为根的左子树和右子树，由此得到的二叉树，称为描述二分查找的判定树或比较树。二分查找的平均查找长度为log2(n+1)-1,所以时间复杂度为O(log2n)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200615205953477.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70