常见查找算法

文章目录

测试数组

let arr = []
  for(let i =0;i < 500000;i++){
    arr.push(i)
  }
exports.arr = arr

顺序查找

顺序查找就是简单的遍历并比较是否相等

let testArr = require('../testArr').arr
let data = 49999

function searchData (array, data) {
  for (let index = 0; index < array.length; index++) {
    const element = array[index];
     if (element === data) {
      console.log(`${data}在数组的第${index}个`)
      return
    }
  }
  console.log(`查找失败`)
}

console.time('sortTime')
searchData(testArr, data)
console.timeEnd('sortTime')

二分查找(折半查找)

注意：二分查找是基于有序数组的情况

let testArr = require('../testArr').arr
let data = 49999

function searchData (array, data) {
  let low = 0
  let high = array.length - 1
  while (low < high) {
    let mid = parseInt(( low + high ) / 2)
    if (data> array[mid] ) {
      low = mid
    }
    if (data < array[mid]) {
      high = mid 
    }
    if (array[mid] === data) {
      console.log(`${data}在数组的第${mid}个`)
      return
    }
  }
  console.log(`查找失败`)
}

console.time('sortTime')
searchData(testArr, data)
console.timeEnd('sortTime')