Utilisation de la recherche binaire pour trouver toutes les occurrences d'un nombre dans un tableau trié en utilisant Javascript

Votre code répète le décompte pour chaque occurrence.

Supposons que nous ayons un tableau [5,5,5,5], 5. Commençant par 0,3 comme début, fin. Milieu = 1 donc l'occurrence deviendra 1 (d'abord si) puis à l'intérieur de la boucle while, L'autre partie sera calculée pour que l'occurrence devienne 2. maintenant vous commencez par 2,3 donc mid est 2 qui est à nouveau compté par la première instruction if.

Autre approche:

• Créez une fonction de recherche binaire qui renvoie la position de l'élément. Courir la première fois jusqu'à ce que vous trouviez mi dire x;
• réexécutez-le de 0 à x-1 et x + 1 jusqu'à la fin
• Faites ceci jusqu'à ce qu'il n'y ait pas de résultat pour la première moitié de la recherche et seconde moitié de la recherche
• Les derniers résultats connus des recherches peuvent être soustrait pour compter le nombre d'occurrences.

Exemple pour mon approche.

[1, 2, 3, 4, 4, 4, 4, 4, 4, 5, 6, 7, 8]

binarysearch = bs (arr, val, start, end) = renvoie la position de val dans le tableau 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

Cela devrait vous donner le décompte. Je doute un peu de la complexité mais cela semble être c log n où c

Essayez d'utiliser ceci mais la complexité ne sera pas O (n) dans ce cas, un BST qui permet à l'un des enfants droit ou gauche d'être égal au nœud racine, nécessitera des étapes de calcul supplémentaires pour terminer une recherche où des nœuds dupliqués sont autorisés. Les clés en double sont-elles autorisées dans la définition de la recherche binaire arbres?

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));

Cette question est une suggestion dans la barre latérale, alors que je cherchais une autre question, alors j'ai pensé à l'essayer.

Je ne suis pas un bon programmeur JavaScript de base, mais j'ai légèrement modifié votre code et je pense que le code ci-dessous donne vous corrigez le résultat

{occurence: 4, count: 8}

Sortie dans ma console

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));

Tout bon programmeur JS pourrait éditer et apporter des améliorations à ce code, Je l'apprécierai.