JavaScript — 搜索算法

---

1、顺序搜索

顺序或线性搜索是最基本的搜索算法。它的机制是，将每一个数据结构中的元素和我们要找的元素做比较。

顺序搜索也是最低效的一种搜索算法。

let sequentialSearch = (arr, item) => { // 传入数组和要找到的元素
	for(let i = 0, len = arr.length; i < len; i++) {
		if(item === arr[i]) {
			return i;
		}
	}
	return -1;
}

顺序搜索迭代整个数组，将每个数组元素和搜索项作比较，如果搜索到了，将返回特定值（索引，值，布尔值）。

---

2、二分搜索

这个算法要求被搜索的数据结构已排序。

分为四个步骤：

（1）、选择数组的中间值。

（2）、如果选中值是待搜索值，那么算法执行完毕。

（3）、如果待搜索值比选中值小，则返回步骤1并在选中值的左边的子数组中寻找。

（4）、如果待搜索值比选中值大，则返回步骤1并在选中值的右边的子数组中寻找。

let binarySearch = (arr, item) => {
	arr.quickSort(); // 先从小到大排序
	let low = 0,
		high = arr.length - 1;
		mid, element;
	while(low <= high) {
		mid = ((low + high) / 2);
		element = arr[mid];
		if(element < item) {
			low = mid + 1;
		} else if(element > item) {
			high = mid - 1;
		} else {
			return mid;
		}
	}
	return -1;
}