java之顺序二分查找

2019-05-12

顺序查找与二分查找动图展示

二分查找

百科

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

图示过程

文字叙述过程

二分查找是一种高效的查找算法。它比顺序查找快的多，虽然它需要的条件是数组是有序的。
在查找时，我们先将被查找的数和数组的中间键比较，因为数组是有序的，所有若被查找的数小于数组的中间键则这个数只可能在数组的左部分,然后将中间键的左边数组当作一个数组来进行二分查找。反之，则在数组的右部分，同样将右部分的数组当作一个数组来进行二分查找。若相等，则命中。

代码实现

public static int binarySearch(int arr[], int left, int right, int key) {
	// 递归结束的条件,此时说明递归整个数组，没有找到
	if (left > right) {
		return -1;
	}
	int middle = (left + right) / 2;// 中间的索引
	int middleVal = arr[middle];// 中间的值
	if (key > middleVal) {// 向右递归
		return binarySearch(arr, middle + 1, right, key);
	} else if (key < middleVal) {// 向左递归
		return binarySearch(arr, left, middle - 1, key);
	} else {
		return middle;
	}
}

代码增强版

二分查找的改进，如果数组中有多个相同的元素，全部找出来存到一个链表中并返回他们的数组下标

public static List<Integer> binarySearch2(int arr[], int left, int right, int key) {
		// 递归结束的条件
		if (left > right) {
			return null;
		}
		int middle = (left + right) / 2;// 中间的索引
		int middleVal = arr[middle];// 中间的值
		if (key > middleVal) {// 向右递归
			return binarySearch2(arr, middle + 1, right, key);
		} else if (key < middleVal) {// 向左递归
			return binarySearch2(arr, left, middle - 1, key);
		} else {
			// 定义一个链表，将相同元素添加到一个链表中
			List<Integer> arrayList = new ArrayList<Integer>();
			// 定义临时一个指针变量，实现扫描
			int temp = middle - 1;
			// 实现左扫描
			while (true) {// 退出扫描
				if (temp < 0 || arr[temp] != middleVal) {
					break;
				}
				// 否则，就temp 放入到 arrayList
				arrayList.add(temp); // 添加key到集合中
				temp -= 1;// 左移
			}
			arrayList.add(middle);//把中间找到的添加进去
			// 实现右扫描
			temp=middle+1;
			while (true) { 
				if (temp > arr.length - 1 || arr[temp] != middleVal) {
					break;
				}
				arrayList.add(temp);// 添加key到集合中
				temp += 1;// 右移
			}
			return arrayList;
		}
	}

顺序查找

描述

顾名思义，查到就返回

代码实现

// 基础版线性查找，只返回第一次查找到值的第一个下标
public static int seqSearch(int arr[], int key) {
	for (int i = 0; i < arr.length; i++) {
		if (arr[i] == key) {
			return i;
		}
	}
	return -1;
}

代码实现2

// 加强版线性查找，返回所有查找到数字的所有下标
	// 实现方法，查找到后将下标加入一个集合中
public static List<Integer> seqSearch2(int arr[], int key) {
	List<Integer> arrayList = new ArrayList<Integer>();
	for (int i = 0; i < arr.length; i++) {
		if (arr[i] == key) {
			arrayList.add(i);
		}
		
	}
	return arrayList;
}