/**assume the array is [3, 0, 0, 0, 0, 0, 0, 0, 0 , 9].
     * 1-lets assume that previous bottom and previous top are probableBottom and probableTop respectively
     * so that we can keep track where should we back if discovering that we are  in wrong direction.
     * 2-check that we are in the wrong direction or not,how can we check?
     * actually  the array is almost sorted so assume the middle index is 4 that equal 0(arr[4]=0)
     * and key=9 so according to the binary search algorithm it will move to right(9>0)
     * any positive number is more than zero so it will move to right often.
     * so the new  start=4+1 and  end=9 the array is quite sorted so the key should belong to
     * range [start,end] and if the key is less than start then it will not belong this range ([start,end])
     * so it should go back as he is in wrong direction these can be made  if (key<arr[bottom]) then
     *  middle=(probablBottom+probablTop)/2;//go back to previous range .you should store the previous top and bottom in
     *  each once so when test (key>arr[middle]) you should make probablTop=middle-1
     *  and the rest off binary search algorithms is the same
     **/
    public static int search3(Integer key, int [] arr){
        int middle;
        int top=arr.length-1;
        int bottom=0;
        int probablTop=top,probablBottom=bottom;
        while (top >= bottom) {
           middle=(top+bottom)/2;
           if (key<arr[bottom]){
              middle=(probablBottom+probablTop)/2;
           }
           if (arr[middle]==key)
               return middle;
           else if (key>arr[middle]){
               probablTop=middle-1;
               bottom=middle+1;
           }
           else {
               top = middle - 1;
           }
        }
        return -1;
    }