搜索算法

顺序（或线性）搜索

let sequentialSearch = function (item, array) {
    for (let i = 0; i < array.length; i++) {
        if (item === array[i]) { return i }
    }
    return -1
}

二分搜索

let binarySearch = function (item, array) {
    quickSort(array) 

    let left = 0,
        right = array.length - 1, // 这里要减 1
        mid
    while (left <= right) {
        mid = Math.floor((left + right) / 2)
        if (item < array[mid]) { right = mid - 1 } 
        else if (item > array[mid]) { left = mid + 1 }
        else { return mid }
    }
    return -1
}

工具函数

大专栏搜索算法>

// 生成数组
let generateNonSortedArray = (max, length) => {
    let temp = []
    for (let i = 0; i < length; i++) {
        temp.push(Math.ceil(Math.random() * max))
    }
    return temp
}

// 快速排序
let quickSort = (array) => {
    quick(0, array.length - 1, array)
}

let quick = (left, right, array) => {
  let index
  if (array.length > 1) {
    index = partition(left, right, array)
    // 以主元为界，分两组
    // 要有停止递归继续执行的判断条件
    if (left < index - 1) { quick(left, index - 1, array) }
    if (right > index) { quick(index, right, array) }
  }
}

let partition = (left, right, array) => {
  // 以正中间的元素为主元
  let pivot = array[Math.floor((left + right) / 2)],
      l = left, // 左指针，从前往后遍历左边
      r = right // 右指针，从后往前遍历右边

  // 找到前面比主元大的元素和后面比主元小的元素，两者交换
  while (l <= r) {
    while (array[l] < pivot) { l += 1 }
    while (array[r] > pivot) { r -= 1 }
    if (l <= r) { 
      swap(l, r, array)
      l += 1
      r -= 1
    }
  }
  // 左指针大于右指针时，返回左指针，作为下一次遍历的主元
  return l
}
// 快速排序结束

// 交换两个值
let swap = (i, j, array) => {
  [array[i], array[j]] = [array[j], array[i]]
}

参考链接

loiane/javascript-datastructures-algorithms