数据结构与算法简述二分查找法

旧城等待， 2022-03-31 04:20 243阅读 0赞

二分法查找：二分查找又称折半查找，每次查找，将数据分为两个部分，逐渐缩小查找范围，直到查到数据。

时间复杂度为log2n。

使用二分查找要求：一是必须是顺序存储数据结构，二按关键字有序排列。

/**
     * 二分查找法
     */
    public class BinarySearch {
    
    	/**
    	 * 循环实现
    	 */
    	public static int search(int[] t, int d) {
    		int lowIndex = 0;
    		int highIndex = t.length - 1;
    		while(lowIndex <= highIndex) {
    			int midIndex = (lowIndex + highIndex) / 2;
    			if (t[midIndex] == d) {
    				return midIndex;
    			} else if (d < t[midIndex]) {
    				highIndex = midIndex - 1;
    			} else if (d > t[midIndex]) {
    				lowIndex = midIndex + 1;
    			}
    		}
    		return -1;
    	}
    	
    	/**
    	 * 递归实现
    	 */
    	public static int search2(int[] t, int d,int high,int low) {
    		int mid = (high+low)/2;
    		if(low > high) {
    			return -1;
    		}
    		if(d == t[mid]) {
    			return mid;
    		}else if(d > t[mid]) {
    			return search2(t, d, high, mid+1);
    		}else if(d < t[mid]) {
    			return search2(t, d, mid-1, low);
    		}
    		return -1;
    		
    	}
    	
    	public static void main(String[] args) {
    		int[] t = {1,4,5,7,9,11,45,56};
    		System.out.println("re:" + BinarySearch.search(t, 56));
    		System.out.println("re2:" + BinarySearch.search2(t, 11, t.length-1, 0));
    	}
    }

二分查找法优缺点

优点是查找次数少，性能较高。

缺点是查询的数据表要为有序排列，有一定的局限性。

二分查找适用于不经常变动查找频繁的有序列表。

发表评论取消回复

表情：

评论列表（有 0 条评论，243人围观）

还没有评论，来说两句吧...

相关阅读

相关 python算法与数据结构-二分查找算法

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIx

我会带着你远行/ 2023年10月06日 13:26/ 0 赞/ 24 阅读

相关数据结构-查找-二分查找法

二分查找法如果要查找的数据已经实现拍好了顺序，就可以使用二分查找法来进行查找。二分查找法是将数据分割成两等分，再比较键值与中间值的大小，如果键值小于中间值，就可以确定要

╰+哭是因爲堅強的太久メ/ 2023年10月04日 16:28/ 0 赞/ 72 阅读

相关【数据结构与算法】二分查找

一、什么是二分查找？二分查找针对的是一个有序的数据集合，每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。二、

客官°小女子只卖身不卖艺/ 2022年11月28日 13:33/ 0 赞/ 155 阅读

相关数据结构与算法--二分查找算法

二分查找是折半查找，根据中间值一分为二。如果目标值大于中间值，那么就舍弃左边的从中间值的右边查找。如果目标值小于中间值，那么就舍弃右边的从中间值开始左边查找。注意：二分查

Dear 丶/ 2022年10月06日 02:56/ 0 赞/ 292 阅读

相关【数据结构与算法】二分查找

基本思想首先将给定的值K与表中中间位置元素比较，若相等，则查找成功；若不等，则所需查找的元素只能在中间数据以外的前半部分或者后半部分，缩小范围后继续进行同样的查找，如

短命女/ 2022年08月11日 00:55/ 0 赞/ 230 阅读

相关数据结构与算法-二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。二分查找的基本

Love The Way You Lie/ 2022年05月29日 10:00/ 0 赞/ 246 阅读

相关数据结构与算法简述二分查找法

二分法查找：二分查找又称折半查找，每次查找，将数据分为两个部分，逐渐缩小查找范围，直到查到数据。时间复杂度为log2n。使用二分查找要求：一是必须是顺序存储数据结构，二

旧城等待，/ 2022年03月31日 04:20/ 0 赞/ 244 阅读

相关二分查找-查找算法-数据结构与算法

介绍二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

迷南。/ 2022年02月12日 12:23/ 0 赞/ 343 阅读

相关 JS数据结构与算法——二分查找

/ 二分查找 @param {Array} arr 待查找数组,数组需要已按照从小到大排序 @param {Any} x 待查找项 @return {Numbe

心已赠人/ 2022年02月02日 02:51/ 0 赞/ 296 阅读

相关二分查找（数据结构与算法）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXh

谁借莪１个温暖的怀抱￠/ 2021年12月23日 23:49/ 0 赞/ 329 阅读