搜索

搜索是一场未知的冒险，我们或许需要走遍神秘空间的每个角落，又或许可以快速锁定目标。 在这场寻觅之旅中，每一次探索都可能得到一个未曾预料到的答案。

二分查找

二分查找是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直到找到目标元素或搜索范围为空。

给定一个长度为 n 的数组 nums，元素按从小到大的顺序排列且不重复。请查找并返回元素 target 在该数组中的索引。若数组中不存在该元素，则返回-1。

// 不断移动l与r的位置
function binarySearch(arr = [], target) {
	let l = 0,
		r = arr.length - 1;
	while (l <= r) {
		// 取中值：在其他语言中数据量过大时L+R可能溢出，所以使用l + (r - l) / 2
		let mid = Math.floor(l + (r - l) / 2);
		if (arr[mid] > target) r = mid - 1;
		if (arr[mid] < target) l = mid + 1;
		if (arr[mid] == target) return mid;
	}
	return -1;
}

let res = binarySearch([1, 2, 3, 4, 52, 124, 41], 52);
console.log(res); // 4

时间复杂度为 O(log n)：在二分循环中，每次缩小一半的范围，所以时间复杂度为 log n。 空间复杂度为 O(1)：l 与 r 均使用常数大小的空间。

区间表示方法

上述案例为双闭区间，常见的区间表示还有“左闭右开”、“左开右闭”、“左开右开”等。下例为左闭右开区间的二分查找：区间定义为[0,n)，该情况下 l=r 时为空数组。

/* 二分查找 */

// 双闭区间
function binarySearch(arr = [], target) {
	let l = 0,
		r = arr.length - 1;
	while (l <= r) {
		// 取中值
		let mid = Math.floor(l + (r - l) / 2);
		if (arr[mid] > target) r = mid - 1;
		if (arr[mid] < target) l = mid + 1;
		if (arr[mid] == target) return mid;
	}
	return -1;
}

let res = binarySearch([1, 2, 3, 4, 52, 124, 41], 52);
console.log(res);

// 左闭右开：一种写法如下，另外一种可以将末尾元素删除，其余写法类似于双闭合区间
function binarySearchRightOpen(arr = [], target) {
	let l = 0,
		r = arr.length;
	while (l < r) {
		// 取中值
		let mid = Math.floor(l + (r - l) / 2);
		if (arr[mid] > target) r = mid;
		if (arr[mid] < target) l = mid + 1;
		if (arr[mid] == target) return mid;
	}
	return -1;
}

let res2 = binarySearchRightOpen([1, 2, 3, 4, 52, 124, 41], 52);
console.log(res2);

// 左开右闭：可以将l初始为1，其余类似于双闭合区间

// 左开右开：删除首尾元素，其余类似于双闭合区间

优点与局限性

二分查找在时间和空间方面都有很好的性能。

• 二分查找的时间效率很高，在大数据量的情况下具有显著优势。例如处理 n=$2^{20}$时，线性查找需要$2^{20}$=1048576 轮循环，而二分查找只需要 20 轮。
• 二分查找无需多余空间，相较于需要借助额外空间的搜索算法（例如哈希算法），二分查找更加节省空间。

但是二分查找并非适用于所有情况，主要原因有以下：

• 二分查找仅适用于有序数据，在无序数据时，为了使用二分查找还得先进行排序，但是排序算法的时间复杂度通常为 O(n logn)，比线性查找和二分查找都要高。对于频繁插入元素的场景，为了保存数据的有序性，需要将元素插入到特定位置，时间复杂度也为 O(n)，也是开销很大的。
• 二分查找仅适用于数组。二分查找需要跳跃式访问元素，而链表中执行跳跃式访问效率较低，因此不适合将二分查找用于链表或基于链表实现的数据结构中。
• 小数据量下，线性查找性能更佳。

二分查找插入点

二分查找不仅可用于搜索目标元素，还可用于很多变种问题，例如搜索目标的插入位置。

无重复元素的情况

给定一个长度为 n 的有序数组 nums 和一个元素 target，数组不存在重复元素。现将 target 插入数组 nums 中，并保持其有序性。若数组中已存在元素 target，则插入到其左方，最终返回插入后的 target 在数组中的索引。

function binarySearchInsert(arr = [], target) {
	let l = 0,
		r = arr.length - 1;

	while (l <= r) {
		// 获取中值索引
		let middle = Math.floor(l + (r - l) / 2);

		if (arr[middle] > target) {
			r = middle - 1;
		} else if (arr[middle] < target) {
			l = middle + 1;
		} else {
			// 重复时，插入左边，即该数组中重复值的索引
			return middle;
		}
	}
	return l;
}

let res = binarySearchInsert([1, 2, 3, 6, 8], 12);
console.log(res); // 5

存在重复值情况

// 存在重复值
function binarySearchIntserRepeat(arr = [], target) {
	let l = 0,
		r = arr.length - 1;

	while (l <= r) {
		let middle = Math.floor(l + (r - l) / 2);
		if (arr[middle > target]) {
			r = middle - 1;
		} else if (arr[middle] < target) {
			l = middle + 1;
		} else {
			// 找到第一个相同的，向左线性遍历，直到找到最左侧的
			let leftArr = arr.slice(0, middle + 1);
			let index = null;
			leftArr.map((el, edex) => {
				if (el == target && index == null) index = edex;
			});
			return index;
		}
	}

	return l;
}

/* 更简单写法 */
function binarySearchInsertion(nums, target) {
	let i = 0,
		j = nums.length - 1; // 初始化双闭区间 [0, n-1]
	while (i <= j) {
		const m = Math.floor(i + (j - i) / 2); // 计算中点索引 m, 使用 Math.floor() 向下取整
		if (nums[m] < target) {
			i = m + 1; // target 在区间 [m+1, j] 中
		} else if (nums[m] > target) {
			j = m - 1; // target 在区间 [i, m-1] 中
		} else {
			j = m - 1; // 首个小于 target 的元素在区间 [i, m-1] 中
		}
	}
	// 返回插入点 i
	return i;
}
let repeat = binarySearchInsertion([1, 2, 3, 3, 4, 6, 7, 8], 3);
console.log(repeat);

二分查找边界

查找左边界

给定一个长度为 n 的有序数组 nums，其中可能包含重复元素，请返回数组中 target 在数组中最左侧的索引，若不存在则返回-1。

/* 二分查找左边界 */
function binarySearchInsert(nums = [], target) {
	// 先执行二分查找插入
	let l = 0,
		r = nums.length;
	while (l <= r) {
		let middle = Math.floor(l + (r - l) / 2);
		if (nums[middle] > target) {
			r = middle - 1;
		} else if (nums[middle] < target) {
			l = middle + 1;
		} else {
			r = middle - 1;
		}
	}

	return l;
}

function binarySearchLeft(nums = [], target) {
	// 二分查找插入找到的就是最左侧索引
	let i = binarySearchInsert(nums, target);

	if (nums[i] != target) return -1;

	return i;
}

let res = binarySearchLeft([1, 2, 2, 3, 4, 35], 9);
console.log(res);

查找右边界

/* 右边界：找到数组nums中目标target的最右侧索引，若不存在则返回-1 */
function binarySearchRight(nums = [], target) {
	let l = 0,
		r = nums.length - 1; // 希望最终的右边界指向的是最后一个等于目标值的元素位置

	while (l <= r) {
		let middle = Math.floor(l + (r - l) / 2);
		if (nums[middle] > target) {
			r = middle - 1;
		} else if (nums[middle] < target) {
			l = middle + 1;
		} else {
			l = middle + 1;
		}
	}

	if (nums[r] != target) return -1;
	return r;
}

let res = binarySearchRight([1, 2, 3, 4, 5], 5);
console.log(res);

哈希优化策略

在算法题中，我们常通过将线性查找替换为哈希查找来降低算法的时间复杂度。

给定一个整数数组nums和一个目标元素target，请在数组中搜索和为target的两个元素，并返回它们的索引。返回任意一个解即可。

线性查找：以时间换空间

直接遍历所有的可能性组合，开启两层循环，每轮判断和是否为target。

/* 哈希优化-线性查找 */

function lineSearch(nums = [], target) {
	for (let i = 0; i < nums.length; i++) {
		for (let j = i; j < nums.length; j++) {
			if (nums[i] + nums[j] == target) {
				return [i, j];
			}
		}
	}

	return [];
}

let res = lineSearch([2, 3, 4, 5], 7);
console.log(res);

该方法时间复杂度为O($n^{2}$)，空间复杂度为O(1)，数据量过大时非常耗时。

哈希查找：以空间换时间

借助一个哈希表，键值对分别为数组元素和索引，循环遍历数组，每轮执行以下操作：

• 判断target-nums[i]是否在哈希表中，存在则返回两个元素的索引
• 将i和nums[i]存储于哈希表中

/* 哈希优化-哈希表 */
function hashMap(nums = [], target) {
	let map = new Map();
	for (let i = 0; i < nums.length; i++) {
		let val = target - nums[i];
		if (map.has(val)) {
			return [i, map.get(val)];
		} else {
			map.set(nums[i], i);
		}
	}

	return [];
}

let res2 = hashMap([1, 2, 3, 4], 5);
console.log(res2);

时间复杂度为O(n)，将时间复杂度从O($n^{2}$)将为了O(n)，大幅提升效率，而空间复杂度为O(n)。

重识搜索算法

搜索算法用于数据结构中搜索一个或一组满足条件的元素。

搜索算法可根据实现思路分为两类：

• 通过遍历数据结构来定位目标元素，例如数组、链表、树和图的遍历等。
• 利用数据组织结构或数据包含的先验信息，实现高效元素查找，例如二分查找、哈希查找和二叉搜索树等，

暴力搜索

暴力搜索通过遍历数据结构的每个元素来定位目标元素。

• “线性搜索”适用于数组和链表等线性数据结构。它从数据结构的一端开始，逐个访问元素，直到找到目标元素或到达另一端时还未找到目标元素为止。
• “广度优先搜索”和“深度优先搜索”是图和树的两种遍历策略。广度优先搜索从初始节点开始逐层搜索，由近及远地访问各个节点。深度优先搜索从初始节点开始，沿着一条路走到尽头，再回溯并尝试其他路径，直到遍历完整个数据结构。

暴力搜索的优点是简单且通用性好，无需对数据做预处理和借助额外的数据结构。但是此类算法是时间复杂度为O(n)，在数据量过大时性能较差。

自适应搜索

自适应搜索利用数据的特有属性(例如有序性)来优化搜索过程，从而更高效的定位目标元素。

• “二分查找”利用数据的有序性实现高效查找，仅适用于数据
• “哈希查找”利用哈希表将搜索数据和目标数据建立为键值对映射，从而实现查询操作。
• “树查找”利用特定的树结构(例如二叉搜索树)中，基于比较节点值来快速排除节点，从而定位元素。

此类算法的优先是效率高，时间复杂度可达O($log {n}$)甚至是O(1)。但是此类算法一般需要对数据做预处理。例如二分查找中需要先对数组进行排序，哈希查找和树查找都需要借助额外的数据结构，维护这些数据结构也需要额外的时间和空间开销。

自适应搜索算法常被称为查找算法，主要用于在特定数据结构中快速检索目标元素。

搜索方法选取

给定大小为n的一组数据，我们可以用线性搜索、二分查找、树查找、哈希查找等多个方法从中搜索目标元素，各工作原理如下图：

多种搜索策略

线性搜索

• 通用性好，无需任何数据预处理操作。
• 适用于数据量较小的数据。
• 适用于数据更新频繁的场景。

二分查找

• 适用于大数据量的情况下，效果表现稳定，最差时为O(log ${n}$)
• 数据量不能过大，因为存储数组需要连续的内存空间。
• 不适合于高频增删的场景，应为维护有序数组的开销较大。

哈希查找

• 适合对查询性能很高的场景，平均时间复杂度为O(1)。
• 不适合需要有序数据或范围查找的场景，因为哈希表无法维护数据的有序性。
• 对哈希函数和哈希冲突处理策略依赖很高，具有较大的劣化风险。
• 不适合数据量过大的情况，因为哈希表需要额外的空间来最大程度减少哈希冲突，从而提供良好的查询性能。

树查找

• 适合海量数据，应为树节点在内存中是分散存储的。
• 适合需要维护有序数据或范围查找的场景。
• 在持续增删节点的过程中，二叉搜索树可能会倾斜，时间复杂度劣化为O(n)。
• 若使用AVL树或红黑树，则各种操作可在O(log ${n}$)效率下稳定运行，但是维护树的平衡会造成额外的开销。