关于算法:算法搜索

顺序搜索

思路径

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) 没有应用额定的空间