import java.io.*;

import java.lang.reflect.Array;

import java.util.Arrays;

import java.util.Collection;

class test

{

    public static void main (String[] args) throws java.lang.Exception

    {

        int[] B = {6,7,8,9,1,2,3,4,5};

        int[][] c = {{1,   3,  5,  7},{10, 11, 16, 20}, {23, 30, 34, 50}};

        System.out.println(search_mini(B));

        System.out.println(search(B,1));

        System.out.println(Arrays.toString(search_2d_matrix(c,30)));

    }

    public static int[] search_2d_matrix(int[][] matrix, int target){

        int row = matrix.length, column = matrix[0].length;

        int begin = 0, end = row * column ;

        int[] result = {-1, -1};

        while (begin + 1 < end) {

            int mid = (begin +  end) / 2;

            int number = matrix[mid / column][mid % column];

            if (number == target) {

                result[0] = mid / column;

                result[1] = mid % column;

                return result;

            } else if (number < target) {

                begin = mid;

            } else {

                end = mid;

            }

        }

        return result;

    }

    public static int search_mini(int[] A){

        int begin = 0, end = A.length - 1;

        while (begin < end && A[begin] >= A[end]) {

            int mid = (begin + end) / 2;

            if (A[mid] > A[end]) {

                begin = mid + 1;

            } else if (A[mid] < A[begin]) {

                end = mid;

            } else {   // A[begin] == A[mid] == A[end]

             begin = begin + 1;

            }

        }

         return A[begin];

    }

    public static int search(int[] A, int target){

        int begin = 0;

        int end = A.length ;

        while(begin < end){

            int p = (end + begin) / 2;

            if(A[p] == target) return p;

            else if(A[p] > A[begin]  ){

                if(target >= A[begin] && target < A[p]){

                    end = p;

                }

                else begin = p + 1;

            }

            else{

                if(target > A[p] && target <= A[end - 1] ){

                    begin = p + 1;

                }

                else end = p;

            }

        }

        return -1;

    }

}