import java.util.Random;

class Main
{
    public static void main(String[] args)
    {
        int taille;
        int[] tab;
        Random r = new Random();

        taille=100000;
        tab=new int[taille];
        for(int i = 0; i<tab.length; i=i+1)
        {
            tab[i] = r.nextInt();
        }
        
        
//        tri_selection(tab);
        trifusion(tab, 0, tab.length-1);
        verificateur(tab);
        
//        trifusion(tab, 0, tab.length-1);
        
        int position = recherche_dicho(tab, tab[38000]);
        System.out.println(position);
    }
    
    public static void verificateur(int[] T)
    {
        boolean good = true;
        for(int i=0; i<T.length-1; i++)
        {
            if(T[i] > T[i+1])
            {
                good=false;
                break;
            }
        }
        
        if(good) 
        {
            System.out.println("Le tableau est trie");
        }
        else 
        {
            System.out.println("Le tableau n'est PAS trie!!");
        }
    }
    
    
    
    public static int position_plus_grand(int[] T, int limite_a_ne_pas_depasser)
    {
        int max = 0;
        for(int i=1; i<=limite_a_ne_pas_depasser; i=i+1)
        {
            if(T[i]>T[max]) max=i;
        }
        return max;
    }
    
    public static void tri_selection(int[] T)
    {
        int temp, max;
        for(int i=T.length-1; i>0; i=i-1)
        {
            max=position_plus_grand(T, i);
            
            temp=T[i];
            T[i]=T[max];
            T[max]=temp;
        }
    }


    public static void trifusion(int[] T, int debut, int fin)
    {
        if(fin-debut >= 1)
        {
            int milieu = (fin+debut)/2;
            
            trifusion(T, debut, milieu);
            trifusion(T, milieu+1, fin);
            fusion(T, debut, milieu+1, fin);
        }
    }

    public static void fusion(int[] T, int debut, int milieu, int fin)
    {
        int[] P = new int[ fin - debut + 1 ];
        int i = debut;
        int j = milieu;
        int k = 0;
        for(k=0; k < P.length; k=k+1) 
        {
            if( i<milieu && j<=fin )
            {
                if( T[i] < T[j] )
                {
                    P[k] = T[i];
                    i = i+1;
                }
                else
                {
                    P[k] = T[j];
                    j = j+1;
                }
            }
            else if (i >= milieu)
            {
                P[k] = T[j];
                j = j+1;
            }
            else
            {
                P[k] = T[i];
                i = i+1;
            }
        }
        
        for(k=0; k < P.length; k=k+1) 
        {
            T[debut+k]=P[k];
        }
    }
    
    
    public static int recherche_lente(int[] tab, int n)
    {
        for(int i=0; i<tab.length; i=i+1)
        {
            if(tab[i] == n)
            {
                return i;
            }
        }
        
        //on a parcouru tout le tableau sans trouver notre élément.
        //on retourn -1
        return -1;
    }
    
    
    public static int recherche_dicho(int[] tab, int n)
    {
        int debut = 0;
        int fin = tab.length-1;
        
        if(tab[fin]==n)
        {
            return fin;
        }
        
        int milieu = (debut+fin)/2;
        if(tab[milieu]==n)
        {
            return milieu;
        }
        
        while(milieu!=debut)
        {
            if(tab[milieu] > n)
            {
                fin = milieu;
            }
            else
            {
                debut = milieu;
            }
            
            milieu = (debut+fin)/2;
            if(tab[milieu]==n)
            {
                return milieu;
            }
        }
        
        return -1;
    }
    
    
            
}