ricerca binaria e ricerca sequenziale

[veilside]

Ciao ragazzi ho due metodi di ricerca , il primo è la ricerca binaria e l'altra è la ricerca sequenziale. Se volessi Sapere quanti accessi effettuo prima di trovare un elemento con la ricerca binaria e la ricerca sequenziale come dovrei modificare il codice? Cioè come dovrei impostare la variabile che viene incrementata ogni volta che effettuo un accesso e poi la richiamo per conoscere il numero totale di accessi ?

import java.util.Scanner;
public class BinarySearch
{
    private int[] a;
    public BinarySearch(int[] an)
    {
        a=an;
    }
    public void sort()
    {
        for(int i=0;i<a.length;i++)
        {
            int next=a[i];
            int j=i;
            while(j>0 && a[j-1]>next)
            {
                a[j]=a[j-1];
                j--;
            }
            a[j]=next;
        }
    }
    public int Binarysearch(int v)
    {
        int low=0;
        int high=a.length-1;
        while (low<=high)
        {
            int mid=(high+low)/2;
            int diff=a[mid]-v;
            if(diff==0) return mid;
            else if(diff<0) low=mid+1;
            else high=mid-1;
        }
        return -1;
    }

 public int ricercaSequenziale(int key) {
     for (int i=0; i<a.length; i++)
          if (a[i]==key)
              return i;
     return -1;

    public static void main(String[] args)
    {
        int[] b=new int[5];
        Scanner in=new Scanner(System.in);
        for(int i=0;i<5;i++)
        {
            System.out.println("Inserisci un intero:");
            int e=in.nextInt();
            b[i]=e;
        }
                BinarySearch t=new BinarySearch(b);
        t.sort();
        System.out.println("Cerca l'intero:");
        int y=in.nextInt();
        System.out.println("Il risultato della ricerca e':"+t.Binarysearch(y));
        System.out.println("il risultato della ricerca e':"+t.ricercaSequenziale(y));

    }
}

[Celebron]

Originariamente inviato da veilside
Ciao ragazzi ho due metodi di ricerca , il primo è la ricerca binaria e l'altra è la ricerca sequenziale. Se volessi Sapere quanti accessi effettuo prima di trovare un elemento con la ricerca binaria e la ricerca sequenziale come dovrei modificare il codice? Cioè come dovrei impostare la variabile che viene incrementata ogni volta che effettuo un accesso e poi la richiamo per conoscere il numero totale di accessi ?

import java.util.Scanner;
public class BinarySearch
{
    private int[] a;
    public BinarySearch(int[] an)
    {
        a=an;
    }
    public void sort()
    {
        for(int i=0;i<a.length;i++)
        {
            int next=a[i];
            int j=i;
            while(j>0 && a[j-1]>next)
            {
                a[j]=a[j-1];
                j--;
            }
            a[j]=next;
        }
    }
    public int Binarysearch(int v)
    {
        int low=0;
        int high=a.length-1;
        while (low<=high)
        {
            int mid=(high+low)/2;
            int diff=a[mid]-v;
            if(diff==0) return mid;
            else if(diff<0) low=mid+1;
            else high=mid-1;
        }
        return -1;
    }

 public int ricercaSequenziale(int key) {
     for (int i=0; i<a.length; i++)
          if (a[i]==key)
              return i;
     return -1;

    public static void main(String[] args)
    {
        int[] b=new int[5];
        Scanner in=new Scanner(System.in);
        for(int i=0;i<5;i++)
        {
            System.out.println("Inserisci un intero:");
            int e=in.nextInt();
            b[i]=e;
        }
                BinarySearch t=new BinarySearch(b);
        t.sort();
        System.out.println("Cerca l'intero:");
        int y=in.nextInt();
        System.out.println("Il risultato della ricerca e':"+t.Binarysearch(y));
        System.out.println("il risultato della ricerca e':"+t.ricercaSequenziale(y));

    }
}

beh banalmente nella ricerca sequenziale il numero di accessi è dato dall'indice (interno al for) con cui scorri il vettore. Appena trova il valore che cerchi esce dal for con quell'indice bloccato (nel tuo caso però, dove l'indice è dichiarato all'interno del for stesso, appena esce dal for risulta fuori dal contesto).

In quella binaria, visto che usi un while, è sufficiente che crei un indice fittizio esterno che inizializzi a zero e che all'interno del while viene incrementato ogni volta.

[veilside]

Dunque ho messo la variabile accessi all'interno del while, va bene in questa maniera?
Come potrei richiamarla dal main e quindi restituirmi il numeri di accessi che ho effettuato?

 public int Binarysearch(int v)
    {
        int low=0;
        int high=a.length-1;
        int accessi = 0;
        while (low<=high)
        {
            int mid=(high+low)/2;
            int diff=a[mid]-v;
            if(diff==0) 
            	return mid;
            else if(diff<0)
             low=mid+1;
            else high=mid-1;
            accessi++;
        }
        return -1;
       
    }