class HalfSearchTest
{
        public static void main(String[] args)
        {
                int[] arr={3,4,5,6,7};
                int[] arr1={7,6,5,4,3};
                int a=halfSearch(arr,5);
                System.out.println("a="+a);
                int b=halfSearch(arr1,5);
                System.out.println("b="+b);
        }

        public static int halfSearch(int[] arr,int key)
        {
                int min=0,max=arr.length-1,mid;
                while (min<=max)
                {
                        mid=(min+max)>>1;
                        if (arr[min]<arr[max])
                        {
                                if (key>arr[mid])
                                        min=mid+1;
                                else if (key<arr[mid])
                                        max=mid-1;
                                else
                                        return mid;
                        }
                        else if (arr[min]>arr[max])
                        {
                                if (key>arr[mid])
                                        max=mid-1;
                                else if (key<arr[mid])
                                        min=mid+1;
                                else
                                        return mid;
                        }
                        else
                        {
                                if (key==arr[min])
                                        return min;
                                else
                                        return -1;
                        }
                }
                return -1;
        }
}



class ArrayDubbleTest
{
        public static void main(String[] args)
        {
                int[][] arr={{5,6,2,9,1},{3,9,5,6,4},{3,8,7,6,9}};
                print(arr);
                sort(arr);
                print(arr);
        }
        /*
        [[5,6,2,9,1],[3,9,5,6,4],[3,8,7,6,9]]
        [[1,2,5,6,9],[3,4,5,6,9],[3,6,7,8,9]]
        */

        public static void print(int[][] arr)
        {
                System.out.print("[");
                for (int x=0;x<arr.length ;x++ )
                {
                        for (int y=0;y<arr[x].length ;y++ )
                        {                               
                                if (x==arr.length-1&&y==arr[x].length-1)
                                        System.out.print(arr[x][y]+"]]");
                                else if (y==0)
                                        System.out.print("["+arr[x][y]+",");                       
                                else if (y!=arr[x].length-1)
                                        System.out.print(arr[x][y]+",");
                                else
                                        System.out.print(arr[x][y]+"],");
                        }
                }
                System.out.println();
        }


        public static void sort(int[][] arr)
        {
                for (int x=0;x<arr.length ;x++ )
                {
                        for (int y=0;y<arr[x].length ;y++ )
                        {
                                for (int z=y+1;z<arr[x].length ;z++ )
                                {
                                        if (arr[x][y]>arr[x][z])
                                        {
                                                int temp=arr[x][y];
                                                arr[x][y]=arr[x][z];
                                                arr[x][z]=temp;
                                        }
                                }
                        }
                }
        }
}

class HalfSearchTest
{
        public static void main(String[] args)
        {
                int[] arr={3,4,5,6,7};
                int[] arr1={7,6,5,4,3};
                int a=halfSearch(arr,5);
                System.out.println("a="+a);
                int b=halfSearch(arr1,5);
                System.out.println("b="+b);
        }

        public static int halfSearch(int[] arr,int key)
        {
                int min=0,max=arr.length-1,mid;
                while (min<=max)
                {
                        mid=(min+max)>>1;
                        if (arr[min]<arr[max])
                        {
                                if (key>arr[mid])
                                        min=mid+1;
                                else if (key<arr[mid])
                                        max=mid-1;
                                else
                                        return mid;
                        }
                        else if (arr[min]>arr[max])
                        {
                                if (key>arr[mid])
                                        max=mid-1;
                                else if (key<arr[mid])
                                        min=mid+1;
                                else
                                        return mid;
                        }
                        else
                        {
                                if (key==arr[min])
                                        return min;
                                else
                                        return -1;
                        }
                }
                return -1;
        }
}



class ArrayDubbleTest
{
        public static void main(String[] args)
        {
                int[][] arr={{5,6,2,9,1},{3,9,5,6,4},{3,8,7,6,9}};
                print(arr);
                sort(arr);
                print(arr);
        }
        /*
        [[5,6,2,9,1],[3,9,5,6,4],[3,8,7,6,9]]
        [[1,2,5,6,9],[3,4,5,6,9],[3,6,7,8,9]]
        */

        public static void print(int[][] arr)
        {
                System.out.print("[");
                for (int x=0;x<arr.length ;x++ )
                {
                        for (int y=0;y<arr[x].length ;y++ )
                        {                               
                                if (x==arr.length-1&&y==arr[x].length-1)
                                        System.out.print(arr[x][y]+"]]");
                                else if (y==0)
                                        System.out.print("["+arr[x][y]+",");                       
                                else if (y!=arr[x].length-1)
                                        System.out.print(arr[x][y]+",");
                                else
                                        System.out.print(arr[x][y]+"],");
                        }
                }
                System.out.println();
        }


        public static void sort(int[][] arr)
        {
                for (int x=0;x<arr.length ;x++ )
                {
                        for (int y=0;y<arr[x].length ;y++ )
                        {
                                for (int z=y+1;z<arr[x].length ;z++ )
                                {
                                        if (arr[x][y]>arr[x][z])
                                        {
                                                int temp=arr[x][y];
                                                arr[x][y]=arr[x][z];
                                                arr[x][z]=temp;
                                        }
                                }
                        }
                }
        }
}