关于算法:算法搜索

顺序搜索

思路径

for 循环遍历查找

代码实现

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

时空复杂度

工夫: O(n)
空间: O(1) 没有应用额定的空间

二分搜寻

思路径

把数组折成两半

代码实现

    Array.prototype.binarySearch = function (n) {
      let low = 0;
      let high = this.length - 1;
      while (low < high) {let mid = Math.floor((low + high) / 2)
        let midElement = this[mid]
        if (n > midElement) {low = mid + 1} else if (n < midElement) {high = mid - 1} else {return mid;}
      }
      return -1;
    }
    const arr = [5, 4, 3, 2, 1];
    var result = arr.binarySearch(3)
    console.log('result', result)

时空复杂度

工夫: O(logN)
空间: O(1) 没有应用额定的空间