二分查找和顺序查找

た入场券 2022-11-12 02:51 238阅读 0赞

顺序查找可以处理有序数组，也可以处理无序数组，依次遍历数组，查找待找元素，其时间复杂度为o(n)；折半查找只能处理有序数组，每次查找的过程中，都会将查找范围缩小一半，其时间复杂度为o(log2n)，以2为底，n的对数。

### 顺序查找 ###

顺序查找即按照数组的元素下标位置，依次去比对查找，直到找到该元素为止，若循环结束依然未找到该元素，说明数组中没有带查关键字。顺序查找时，理论上最多查找n次，顺序查找的时间复杂度为o(n)。

例如，数组array，有元素\{2，3，4，5，6，7，8，9，10\}，如果要找到元素7在数组中为止，须要遍历6次

![20210322163402450.JPG][]

代码实现

public class SerialSearch {
    
    	public static void main(String[] args) {
    		int[] array = {2, 3, 4, 5, 6, 7, 8, 9, 10};
    		System.out.println(serialSearch(array, 4));
    	}
    	
    	/**
    	 * @顺序查找
    	 * @param arr 数组
    	 * @param key 待查找元素
    	 * @return
    	 */
    	public static int serialSearch(int[] arr, int key) {
    		for (int i=0; i<arr.length; i++) {
    			if (arr[i] == key) {
    				return i;
    			}
    		}
    		
    		return -1;
    	}
    }

### 二分查找 ###

二分查找法又叫做折半查找，要求待查找的序列有序，每次查找都取中间位置的值与关键字进行比较，如果中间位置的值比待查关键字大，则在序列的左半部分继续执行该过程，如果中间位置的值比待查关键字小，则在序列的右半部分继续执行该查找过程，直到找到关键字为止，否则在序列中没有待查关键字。二分查找一直在折半，最终的时间复杂度为o(log2n)，以2为底，n的对数

同样，数组array，有元素\{2，3，4，5，6，7，8，9，10\}，如果要找到元素7在数组中位置，查找3次即可达到

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hZ2kxMjAx_size_16_color_FFFFFF_t_70][]

代码实现

public class BinarySearch {
    
    	public static void main(String[] args) {
    		int[] array = {2,3,4,5,6,7,8,9,10};
    		System.out.println(binarySearch(array, 7));
    	}
    	
    	/**
    	 * @二分查找法
    	 * @param arr 数组
    	 * @param key 待查找元素
    	 * @return
    	 */
    	public static int binarySearch(int[] arr, int key) {
    		int low = 0;
    		int high = arr.length - 1;
    		int mid;
    		while (low <= high) {
    			mid = (high-low)/2+low; // 中间位置
    			if (arr[mid] == key) {
    				return mid;
    			} else if (key > arr[mid]) { // 向右查找
    				low = mid+1;
    			} else { // 向左查找
    				high = mid-1;
    			}
    		}
    		
    		return -1;
    	}
    }

[20210322163402450.JPG]: /images/20221022/cd21b20989cd43d880942a148a10744c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hZ2kxMjAx_size_16_color_FFFFFF_t_70]: /images/20221022/3e8054e4fd70446ea90166baef1aac90.png