我最近开始学习 JavaScript 算法。当我遇到这个问题时，我正在尝试使用二进制搜索，并且我一直在尝试实现它，但我一直遇到困难。 该函数有两个参数(一个排序数组和一个数字)并返回一个包含数字出现次数和计数的对象。我得到的 occurrence 不是数字的正确出现，count 是常量。
这是我到目前为止所做的:
function binarySearchOccurrence(array, element) {
//declare the start index on the left side to zero
let startIndex = 0;
//declare the end index on the right side to the length of array minus 1
let endIndex = array.length - 1;
//set initial count to zero
let count = 0;
let occurrence = 0;
//declare an empty object to hold the result of search and count
const result = {}
//Applying binary search, iterate while start does not meed end
while(startIndex <= endIndex){
//find the middile index
let middle = Math.floor((startIndex + endIndex)/2);
let guessElement = array[middle];
count++;
//if element is present in the middle, increment occurence
if(guessElement === element){
occurrence++;
while(startIndex <= endIndex){
if(guessElement > element){
endIndex = middle - 1;
occurrence++;
break;
} else {
startIndex = middle + 1;
occurrence++;
break;
}
}
//Else look in the left or right side accordingly
} else if (guessElement > element) {
endIndex = middle - 1;
} else {
startIndex = middle + 1;
}
}
result.occurrence = occurrence;
result.count = count;
return result;
}
当我使用这样的数组进行测试时:binarySearchOccurrence([1, 2, 3, 4, 4, 4, 5, 5, 5, 6, 7, 8, 9], 5) 它返回 { occurrence: 6, count: 4 } 而不是 { occurrence: 3, count: 2 };
最佳答案
您的代码对每次出现重复计数。
假设我们有一个数组 [5,5,5,5]，5。从 0,3 开始，结束。 中=1 所以发生将变为 1(第一个如果) 然后在 while 循环中， 将计算 else 部分，因此出现次数变为 2。 现在你从 2,3 开始，所以 mid 是 2，它再次被第一个 if 语句计算。
替代方法:
- 制作一个返回元素位置的二进制搜索函数。运行 第一次直到你找到中间说 x;
- 再次运行 0 到 x-1 和 x+1 结束
- 这样做直到搜索的前半部分没有结果 和搜索的后半部分
- 最近已知的搜索结果可以 减去以计算出现的次数。
我的方法示例。
[1, 2, 3, 4, 4, 4, 4, 4, 4, 5, 6, 7, 8]
binarysearch = bs(arr,val,start,end) = 返回 val 在数组 else -1 中的位置
pos=bs(arr,val,start,end)
a=pos-1
ppos_a=a
while a!=-1 and a-1>=0:
ppos_a=a
a=bs(arr,val,0,a-1)
b=pos+1
ppos_b=b
while b!=-1 and b+1<=len-1:
ppos_b=b
b=bs(arr,val,b+1,len-1)
result = ppos_b-ppos_a
这应该可以让您计数。我对复杂性有点怀疑，但它似乎是 c log n where c << n
关于javascript - 使用二进制搜索查找使用 Javascript 的排序数组中数字的所有出现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54805824/