前言:查找算法在书上分为三种
第一种是比较常用且较为简单的线性表查找;
第二种数表查找;
最后一种是哈希表查找。
线性表查找
顺序查找
就是最为常用的,将关键字依次将给定序列中的各个元素依次比较
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}
// 示例用法
const array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const targetValue = 5;
const result = linearSearch(array, targetValue);
console.log(result); // 4
折半查找
不知道是不是也可以叫做二分查找,局限条件为有序序列,然后每次折半,在折半的范围内查找
function binarySearch(arr, target) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const targetValue2 = 6;
const result2 = binarySearch(sortedArray, targetValue2);
console.log(result2); // 5
评论区