Использование двоичного поиска, чтобы найти все вхождения числа в отсортированном массиве с использованием Javascript

Question

Я недавно начал изучать алгоритмы на 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 };

Answer 1

Попробуйте использовать это, но сложность не будет O (n), в этом случае BST, который позволяет правому или левому потомку быть равным корневому узлу, потребует дополнительных вычислительных шагов для завершения поиска, где дублируются узлыразрешены. Допускаются ли дубликаты ключей в определении деревьев бинарного поиска?

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) {
          endIndex = middle - 1;
          occurrence++;
        } else if (guessElement < element) {
          startIndex = middle + 1;
          occurrence++;
        } else if (guessElement === element) {
         occurrence++;
         count++;

         let searchleft = middle; // searchleft == middile index

         let searchright = middle;// searchright == middile index


//loop while we donot fine integar < element on left and integar > element on rigth;
          while (array[searchright] == guessElement && array[searchleft] == guessElement ) { 


            if (array[searchright] == element) { //if integar right still equal to element 
              searchright = searchright - 1;
              count++;
              occurrence++;
            } else if(array[searchleft] == element) { //if integar left still equal to element 
            searchleft = searchleft + 1;
              count++;
              occurrence++;
            }
          }
        }
        result.occurrence = occurrence;
        result.count = count;
        return result;
      }}

      console.log(binarySearchOccurrence([1, 2, 3, 4, 4, 4, 5, 5, 5, 6, 7, 8, 9], 5));

Answer 2

Этот вопрос является предложением на боковой панели, когда я рассматривал какой-то другой вопрос, поэтому подумал попробовать его.

Я не очень хороший программист на JavaScript, но немного изменил ваш код и думаю,код ниже дает вам правильный результат

function binarySearchOccurrence(array, element, flag) {
            //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 occurence = -1;
            const result = {}
            //Applying binary search, iterate while start does not meed end 
            while (startIndex <= endIndex) { //find the middle index 
                let middle = Math.floor((startIndex + endIndex) / 2);
                count++; //if element is
                //   present in the middle, increment occurence 
                if (array[middle] == element) {
                    occurence = middle;
                    if (flag == "last") {
                        startIndex = middle + 1;
                    } else {
                        endIndex = middle - 1;
                    }
                } else {
                    if (arr[middle] > element) {
                        endIndex = middle - 1;
                    } else {
                        startIndex = middle + 1;
                    }
                }
            }
            result.occurence = occurence;
            result.count = count;
            return result;
        }

        function countOccurence(arr, key) {
            let count = binarySearchOccurrence(arr, key, "last").count + binarySearchOccurrence(arr, key, "first").count;
            let occurence = (binarySearchOccurrence(arr, key, "last").occurence - binarySearchOccurrence(arr, key,
                "first").occurence) + 1;
            let result = {};
            result.occurence = occurence;
            result.count = count;
            return result;
        }
        let arr = [0, 1, 2, 3, 4, 4, 4, 4, 5, 6, 7, 8, 9];
        console.log(countOccurence(arr, 4));

Вывод на мою консоль

{occurence: 4, count: 8}

Любой хороший программист JS может редактировать и улучшать этот код, я буду признателен.

Answer 3

Ваш код повторяет счет для каждого вхождения.

Скажем, мы получили массив [5,5,5,5], 5. Начиная с 0,3 в качестве начала, конца,Mid = 1, поэтому вхождение станет 1 (сначала if), затем внутри цикла while, часть else будет рассчитана таким образом, что вхождение станет 2. Теперь вы начинаете с 2,3, поэтому mid равно 2, что снова считается первым оператором if.

Альтернативный подход:

• Создать бинарную функцию поиска, которая возвращает позицию элемента.Запустите его в первый раз, пока не найдете середину скажем х;
• запустить его снова от 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 в массиве, иначе -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, где c << n </p>