顺序搜索

Array.prototype.search = function (target) {
    for (let i = 0; i < this.length; i += 1) {
        if (this[i] === target) {
            return i;
        }
    }
    return -1;
}
const arr = [5, 4, 3, 2, 1];
console.log(arr.search(0));

二分查找

二分查找需要数组是有序的，1、先从有序数组的最中间元素开始查找，如果和要查找的元素相等，直接返回索引，若不相等则下一步。2、如果指定的元素大于或者小于中间元素，则在大于或小于的那一半区域内查找，重复第一步直到找到目标元素。

不使用递归

// 时间复杂度 O(logn)    空间复杂度为 O(1)
function two_find(arr, val) {
    var min = 0;
    var max = arr.length - 1;
    var mid;
    while (min <= max) {
        mid = Math.floor((min + max) / 2);
        if (val === arr[mid]) {
            return mid;
        } else if (val < arr[mid]) {
            max = mid - 1;
        } else if (val > arr[mid]) {
            min = mid + 1;
        }
    }
    return -1;
}
console.log(two_find([1, 3, 6, 8, 9, 10], 3));
console.log(two_find([1, 3, 6, 8, 9, 10], 5));
console.log(two_find([1, 3, 6, 8, 9, 10], 8));

使用递归

// 虽然使用递归的时间复杂度也为 O(logn)，但是函数递归调用，会消耗内存，所以空间复杂度也为 O(logn)
function two_find(arr, min, max, val) {
    if (min > max) {
        return -1;
    }
    var mid = Math.floor((min + max) / 2);
    if (val === arr[mid]) {
        return mid;
    } else if (val < arr[mid]) {
        max = mid - 1;
        return two_find(arr, min, max, val);
    } else if (val > arr[mid]) {
        min = mid + 1;
        return two_find(arr, min, max, val);
    }
}
console.log(two_find([1, 3, 6, 8, 9, 10], 0,8,3));
console.log(two_find([1, 3, 6, 8, 9], 0,8,5));
console.log(two_find([1, 3, 6, 8, 9], 0,8,6));

题目

猜数字大小

• 使用二分查找

参考