package Search;
import java.util.Scanner;
public class BinarySearch {
    static final int N=15;
    public static void quick(int[] arr, int start, int end) {        
        
           int low = start;   
           int high = end;    
           int pivot = arr[low];      
           while (low < high) {       
           while (low < high && arr[high] >= pivot) {       
               high--;            
               }   
           arr[low] = arr[high];
           while (low < high && arr[low] <= pivot) {     
               low++;       
               }           
           arr[high] = arr[low]; 
           }
           arr[low] = pivot;   
           if (end <= start)
           {          
              return; 
           }    
      quick(arr, start, low - 1); 
      quick(arr, low + 1, end); 
      }     
    static int binarySearch(int a[],int len,int key)
    {
        int mid,low,high;
        low=0;
        high=len;
        mid=(int)(low+high)/2;
        while(low<=high)
        {
            if(a[mid]==key)
            {
                return mid;
            }
            else if(a[mid]<key)
            {
                low=mid++;
            }
            else
                high=mid--;
        }
        return -1;
    }
    public static void main(String[] args)
    {
        int x,n,i;
        int[] array = new int[N];
        
        for(i=0;i<N;i++)
        {
            array[i]=(int)(100+Math.random()*(100+1));
        }
        System.out.println("the original number is :");
        for(i=0;i<N;i++)
        {
            System.out.println(array[i]);
        }
        
        quick(array,0,N-1);
        System.out.println("the sorted array is :");
        for(i=0;i<N;i++)
            {
                System.out.print(array[i]+"\n");
            }
        
        System.out.println("enter the number to look for");
        Scanner input=new Scanner(System.in);
        x=input.nextInt();
        
        n=binarySearch(array,N,x);
        if (n<0)
        {
            System.out.println("number not found");
        }
        else
        {
            System.out.println("the index of number is :"+(n+1));
        }
    }
}