Méthode efficace pour compter les occurrences d'une clé dans un tableau trié

Pour les ménagères de tableau il n'y a pas beaucoup que nous pouvons faire d'autre que la recherche linéaire.

Pour tableau trié, vous pouvez le faire en O(logN) à l'aide d'un peu modifié binaires de recherche:

• Trouver l'index de la première occurrence de
  keyappeler f.
• Trouver l'indice de la dernière occurrence de
  keyappeler l.
• Si le key existe dans le tableau l-f+1
  est la réponse.

Trouver la première occurrence:

arr[i] est la première occurrence de key iff

• arr[i] == key et soit
  • i == 0 ( c'est le premier élément de
    la matrice) ou
  • arr[i-1] != key (ce n'est pas la première
    élément de la matrice et de l'élément de
    il est à gauche est différente)

Vous pouvez légèrement modifier le binaire de recherche pour trouver la première occurrence.
Dans une recherche binaire vous mettre fin à la recherche lorsque vous trouvez arr[mid] == key.
Modifier la condition de sorte que vous mettre fin à la recherche lorsque vous trouvez la première occurrence au lieu de tout événement.

Algorithme:

low = 0
high = arrSize - 1 

while low <=  high

  mid = (low + high) /2

  //if arr[mid] == key         //CHANGE
  if arr[mid] == key AND ( mid == 0 OR arr[mid-1] != key )
    return mid
  //else if ( key < arr[mid] ) //CHANGE
  else if ( key <= arr[mid] ) 
    high = mid - 1
  else
    low = mid + 1        
  end-if

end-while

return -1

De même, vous pouvez trouver la dernière occurrence.

#include<stdio.h>
int binarysearch(int a[],int n,int k,bool searchfirst){
    int result=-1;
    int low=0,high=n-1;
    while(low<=high){
        int mid=(low+high)/2;
        if(a[mid]==k)  {
              result=mid; 
           if(searchfirst)
              high=mid-1; 
            else
              low=mid+1;
    }
    else if(k<a[mid])  high=mid-1;
    else low=mid+1;
    }
    return result;
}

int main(){
    int a[]={1,1,1,2,2,3,3,3,6,6,6,6,6,7,7};
    int n=sizeof(a)/sizeof(a[0]);
    int x=6;
    int firstindex=binarysearch(a,n,x,true);
    printf("%d\n",firstindex);
    if(firstindex==-1){
        printf("elment not found in the array:\n ");
    }
    else {
        int lastindex=binarysearch(a,n,x,false);
        printf("%d\n",lastindex);
        printf("count is = %d", lastindex-firstindex+1);
    }

}

**
Temps de la Complexité = O ( lg N ) où N est la taille du tableau

** Arguments pour binarySearchXXXXX:**

1. int tableau[] est un tableau trié de longueur >= 1
2. int k : clé de recherche

**

package array;

 public class BinarySearchQuestion {

public static int binarySearchFirst(int[] array, int k) {
    int begin = 0;
    int end = array.length-1;
    int mid = -1;
    while (begin <= end) {
        mid = begin + (end - begin) /2;
        if (array[mid] < k) {
            begin = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    //System.out.println("Begin index :: " + begin + " ,  array[begin] " + array[begin]);
    return (begin <= array.length - 1  && begin >= 0 && array[begin] != k) ? -1 : begin;
    //     return begin;
}

public static int binarySearchLast(int[] array, int k) {
    int begin = 0;
    int end = array.length - 1;
    int mid = -1;
    while (begin <= end) {
        mid = begin + (end - begin) /2;
        if (array[mid] > k) {
            end = mid - 1;
        } else {
            begin = mid + 1;
        }
    }
    //System.out.println("Last index end :: " + end + " ,  array[mid] " + array[end]);
    return (end <= array.length - 1  && end >= 0 &&  array[end] != k) ? -1 : end;
    //return end;
}

/**
 * @param args
 */
public static void main(String[] args) {
             //    int[] array = { 0, 1,1,1, 2, 3, 4,4,4,5, 5, 5, 5, 5, 5, 5, 5, 5, 5,5,6,6,6,6, 6, 7, 7, 7,
             //            7, 8, 9 };
            //     int[] array = { -1, 0,1, 1,1,2,3};
    int[] array = {1,1,1};

    int low = binarySearchFirst(array, 1);
    int high = binarySearchLast(array, 1);
    int total = (high >= low && low != -1 && high != -1) ? ( high - low + 1 ): 0;
    System.out.println("Total Frequency " + total);
}

   }

paquet de tableaux;

/*
* Étant donné un tableau trié, trouver le nombre de fois qu'un élément a eu lieu.
* Une recherche binaire O(lgn)
* */

public class NumberOfN {

static int bSearchLeft(int[] arr, int start, int end, int n){

    while(start < end){

        int mid = (start + end)>>1;
        if(arr[mid] < n){
            start = mid + 1;
        }else{
            end = mid;
        }

    }

    return end;
}

static int bSearchRight(int[] arr, int start, int end, int n){

    while(start < end){

        int mid = (start + end)>>1;
        if(arr[mid] <= n){
            start = mid + 1;
        }else{
            end = mid;
        }

    }

    return end;
}

/**
 * @param args
 */
public static void main(String[] args) {

    int[] arr = new int[]{3,3,3,3};
    int n = 3;
    int indexLeft = bSearchLeft(arr, 0, arr.length, n);
    int indexRight = bSearchRight(arr, 0, arr.length, n);
    System.out.println(indexLeft + " " +indexRight);
    System.out.println("Number of occurences: " + (indexRight - indexLeft));
}

}

Si le tableau est trié, oui, la recherche linéaire à partir d'une extrémité à l'autre est aussi bon qu'il obtient.

Cependant, si le tableau est trié, vous pouvez faire mieux qu'en temps linéaire en appliquant binaire ou l'interpolation des techniques de recherche.

Traiter le problème comme le même que le "Trouver le nombre X dans une liste triée", avec le détail", puis balayez de gauche et de droite afin de déterminer combien de fois X apparaît". La première partie, la recherche, le mieux est d'en binaire ou l'interpolation de recherche dans la plupart des cas.

http://en.wikipedia.org/wiki/Interpolation_search

http://en.wikipedia.org/wiki/Binary_search