我正在开发一个函数，该函数应该从整数列表中返回最接近的较低数字到目标。 （即 [1,23,45,67,94,122]，目标 = 96。应返回 94）。我已经多次检查我的代码，试图“捕获错误”，使该函数返回“未定义”，但我一直无法找出原因......当我通过该过程打印出我的变量时，它们都匹配我想要什么，但我的返回值仍然是未定义的。我在想我的问题出在前两个条件中，但是我仍然不知道为什么。有什么线索吗？
这是我的代码：
function binarySearch(arr,target){
var midpoint = Math.floor(arr.length/2);
if (arr[midpoint] === target){
return arr[midpoint];
}
if (arr.length === 1){
return arr[0];
}
if (arr[midpoint] > target){
binarySearch(arr.slice(0,midpoint),target);
}else if (arr[midpoint] < target){
binarySearch(arr.slice(midpoint),target);
}
}
二元搜索([1,23,45,67,94,122],96); => 预期返回值 = 94 // 获取 = 未定义。 :/
因此，原始算法似乎是错误的，选择小于目标的最大值，而不是在数值上最接近目标的值。
这是另一个版本，有点受java版本的启发，但是是为ES6编写的，并且像问题的代码一样递归。
function binarySearch(arr, target, lo = 0, hi = arr.length - 1) {
if (target < arr[lo]) {return arr[0]}
if (target > arr[hi]) {return arr[hi]}
const mid = Math.floor((hi + lo) / 2);
return hi - lo < 2
? (target - arr[lo]) < (arr[hi] - target) ? arr[lo] : arr[hi]
: target < arr[mid]
? binarySearch(arr, target, lo, mid)
: target > arr[mid]
? binarySearch(arr, target, mid, hi)
: arr[mid]
}
console.log(binarySearch([1, 23, 45, 67, 94, 122], 96)) //=> 94
console.log(binarySearch([1, 23, 45, 67, 94, 122], 47)) //=> 45
console.log(binarySearch([1, 23, 45, 67, 94, 122], 207)) //=> 122
console.log(binarySearch([1, 23, 45, 67, 94, 122], 0)) //=> 1执行递归调用时需要添加return语句
function binarySearch(arr,target){
var midpoint = Math.floor(arr.length/2);
if (arr[midpoint] === target){
return arr[midpoint];
}
if (arr.length === 1){
return arr[0];
}
if (arr[midpoint] > target){
return binarySearch(arr.slice(0,midpoint),target);
}else if (arr[midpoint] < target){
return binarySearch(arr.slice(midpoint),target);
}
}
我认为你的算法不会给出正确的结果。 您需要首先找到应插入元素的位置。 这是堆栈溢出链接： O(log n) 算法在排序数组中找到最佳插入位置
function binarySearch(arr,target, l, h){
var midpoint = Math.floor(l+h/2);
if (arr[midpoint] === target){
return midpoint;
}
if (l === h){
return l;
}
if (arr[midpoint] > target){
return binarySearch(arr,target, l,midpoint);
}else if (arr[midpoint] < target){
return binarySearch(arr, target, midpoint,h);
}
}
function binaryclosest(arr, i){
x= abs(target - arr[i])
y = arr[i+1] - target
z = target - arr[i-1]
if(x<y && x<z){
return arr[i]
}
else{
if(y<z)
return arr[i+1]
else
return arr[i-1]
}
}
i = binarySearch(arr, target, l, h)
value = binaryclosest(arr, i)
然后，你应该减去 i-1 和 i+1 取模，然后返回较小者
二分查找法寻找最接近的数字[Python3]
注意：如果您是初学者或热衷于了解其他人解决问题的方法，请阅读本文
def findClosest(n : int, k : int, arr : List[int]) -> int:
start = 0
end = n-1
if n == 1:
return arr[0]
while start < end:
mid = (start + end)//2
if arr[mid] == k:#if k is in arr return k
return k
elif end - start == 1: #finding its closest
dif = abs(arr[start]-k)
if dif >= abs(arr[end]-k):
return arr[end]
return arr[start]
elif arr[mid] < k:
start = mid
elif arr[mid] > k:
end = mid
详细说明：
解决问题时我遵循的步骤
第1步。最初通过看到问题，我用蛮力方法解决了它，但是超出了运行时间限制，然后我看到了这个解决方案所需的时间复杂度。它是 O(log n)然后我意识到它需要二分搜索方法。
第 2 步。我编写了二分搜索的代码，即有 3 个条件，其中一个是检查 arr[mid] == k，其他 2 个条件是更新 mid 变量，在更新 mid 时，我决定包含 mid，因为我们正在找到最近的非精确（在某些测试用例中，如果我们不包括 mid，我们可能无法找到最接近的预期值）
步骤 3.如果 k 包含在给定数组中，则很容易像普通二分搜索程序一样返回它。
第 4 步。如果不包括 k，则我们的开始和结束变量指向其最接近的值，例如，
k=4,arr = [1,2,3,5,6,8,9]
对于每次迭代
1,2,3,5
2,3,5
3,5（最后一次迭代）
现在在本次迭代中开始 = 3，结束 = 5
现在我们应该找到最接近 k(=4) 的那个
第 5 步。为了赶上最后一次迭代，我们添加了一个条件，我花了 2 分钟，发现“开始”和“结束”之间的差异是一个，所以我将其应用为
if end - start == 1:
现在我们的工作即将完成，我们应该决定 arr[start] 或 arr[end] 最接近 k
我们知道abs()返回数字的绝对差，即abs(5-2)=abs(2-5)=3
计算 arr[start] 与 k 的最接近差异
dif = arr[开始] - k
dif = abs(arr[start]-k)
计算 arr[end] 与 k 的最接近差异
abs(arr[结束]-k)
比较 arr[end] 与 k 和 diff 的最接近差异
if dif >= abs(arr[end]-k):
如果上述条件为真，则 arr[end ] 最接近 k，因此返回 arr[end]
否则返回arr[开始]
感谢您的阅读