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

标签 javascript binary-search

我最近开始学习 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/

相关文章:

c++二进制搜索返回(找到)无论用户类型如何

algorithm - 分而治之算法 - 二分搜索变体

performance - 查找附近值的二进制搜索

javascript - 这个简单的字符串是否被认为是有效的 JSON?

javascript - Android发送短信onload JS

javascript - 将 divs 动画化到样式表上定义的位置

javascript - 浏览器不处理报价参数

java - 二分查找算法包含一行我不明白的内容,有人可以帮我解释一下吗?

c++ - 该值应该在 while 循环结束时还是开始时更新?

javascript - 从 EPOS 浏览器发送数据 USB 端口