手写数据结构 之 随机算法 & 搜索算法

function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    const randomIndex = Math.floor(Math.random() * (i + 1));
    [array[i], array[randomIndex]] = [array[randomIndex], array[i]]
  }
  return array;
}
let arr = [3, 4, 2, 8, 5, 5, 2, 0, 6, 6, 3]
console.log(shuffle(arr));

function seqSearch(arr, data) {
  for (var i = 0; i ＜ arr.length; ++i) {
      if (arr[i] == data) {
        return true;
      }
  }
  return false;
}
let arr = [3, 4, 2, 8, 5, 5, 2, 0, 6, 6, 3]
console.log(seqSearch(arr,2));

function binSearch(arr, data) {
  var upperBound = arr.length - 1;
  var lowerBound = 0;
  while (lowerBound <= upperBound) {
    var mid = Math.floor((upperBound + lowerBound) / 2);
    if (arr[mid] < data) {
      lowerBound = mid + 1;
    }
    else if (arr[mid] > data) {
      upperBound = mid - 1;
    }
    else {
      return mid;
    }
  }
  return -1;
}
let arr = [3, 4, 2, 8, 5, 5, 2, 0, 6, 6, 3]
arr = arr.sort((a, b) => a - b)
console.log(binSearch(arr, 0));

const interpolationSearch = (array, value) => {
  const { length } = array
  let low = 0
  let high = length - 1
  let position = -1
  let delta = -1
  while (low < high) {
    // 选择期望比例 delta = (选择的值-最小值)/(最大值-最小值)
    delta = (value - array[low]) / (array[high] - array[low])
    // 参考下标 position = 最小值 + Math.floort((最大值-最小值) * delta )
    position = low + Math.floor((high - low) * delta);
    if (array[position] === value) {
      return position
    }
    if (array[position] < value) {
      low = position + 1
    } else {
      high = position - 1
    }
  }
}
console.log(interpolationSearch([1, 2, 3, 4, 5, 6, 7, 8, 9], 6));