input輸入時判定陣列值

Question

我想在一個input透過陣列中使用二分搜尋,找到最相近的值,

並在input變換成最相近的數值,該如何實現呢？

假設陣列是 [ 4, 7, 8 ] 在input中輸入5 他會自動變成4.

求助大神！


//二分搜尋法
Array.prototype.binary_search = function(low, high, khey) {
if (low > high)
return -1;
var mid = parseInt((high + low) / 2);
if (this[mid] > khey)
return this.binary_search(low, mid - 1, khey);
if (this[mid] < khey)
return this.binary_search(mid + 1, high, khey);
return mid;
};


Answer 1

Array.prototype.binary_search = function (target, low, high) {
  if (this.length <= 1 || target == null) { return this[0] }

  low = low >= 0 ? Math.min(low, this.length - 1) : 0
  high = high >= 0 ? Math.min(high, this.length - 1) : this.length - 1
  if (low > high) { [low, high] = [high, low] }

  if (low === high) { return this[low] }

  const mid = (low + high) / 2 | 0

  if (target === this[mid]) {
    return target
  }

  if (target < this[mid]) {
    if (target >= this[mid-1]) {
      return this[mid] - target < target - this[mid-1] ? this[mid] : this[mid-1]
    } else {
      return this.binary_search(target, low, mid-1)
    }
  }

  // if (target > this[mid]) {
    if (target <= this[mid+1]) {
      return target - this[mid] < this[mid+1] - target ? this[mid] : this[mid+1]
    } else {
      return this.binary_search(target, mid+1, high)
    }
  // }
};

console.log([4, 7, 8].binary_search(5)) // 4
console.log([4, 7, 8].binary_search(6)) // 7
console.log([4, 7, 8].binary_search(7)) // 7
console.log([4, 7, 8].binary_search(10000)) // 8
console.log([4, 7, 8].binary_search(-1)) // 4
console.log([4, 7, 8].binary_search()) // 4
console.log([].binary_search()) // undefined
console.log([].binary_search(5)) // undefined

Answer 2

用迭代比较简单，没使用递归。

Array.prototype.binary_search_clo = function(khey) {
    var low = 0;
    var high = this.length
    var mid = parseInt((high + low + 1) / 2);
    
    while (this[mid] != khey && low < high){
        if (this[mid] > khey){
            high = mid - 1;
        }
        else if (this[mid] < khey){
            low = mid + 1;
        }
        mid = parseInt((high + low) / 2);
    }
    if (mid > 0 && Math.abs(parseInt(this[mid] - khey)) > Math.abs(parseInt(this[mid-1] - khey))){
        mid = mid -1;
    }
    return mid;
};

找到最后了， 要与旁边比较一下，哪个更接近。