javascript - 使用二进制搜索使用Javascript在排序数组中查找数字的所有出现

我最近开始用JavaScript学习算法。当我遇到这个问题时，我正在尝试二进制搜索，并且一直在尝试实现它，但是我仍然遇到困难。 该函数接受两个参数(排序数组和数字)，并返回一个object，其中包含数字的出现和计数。我得到的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-1ppos_a=awhile a!=-1 and a-1>=0: ppos_a=a a=bs(arr,val,0,a-1)b=pos+1ppos_b=bwhile 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其中c