/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package recursion;

/**
 *
 * @author kvaradar
 */
public class Recursion {
    
    static boolean binarySearch(int [] A, int i, int j, int x) {
        // does A[i..j] contain x? A is sorted
        if (i==j) return (A[i] == x);
        
        int k = (i + j)/2;
        if (x == A[k]) {
            return true;
        }
        else if (x < A[k]) {
            // look for x in A[i..(k-1)]
            return binarySearch(A, i, k-1, x);
        }
        else {
            //look for x in A[k+1..j]
            return binarySearch(A, k+1, j, x);
        }
        
    }
    
    static void reverse(int [] A) {
        recReverse(A, 0, A.length - 1);
    }

    static void recReverse(int [] A, int i, int j) {
        //reverse A[i..j]
        if (i < j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
        // swapped A[i] and A[j]
        recReverse(A, i+1, j-1);// tail recursion
        }
    }
    
    static long binaryFib(int n) {
        //return nth Fibonacci number
        if (n <= 1) return n;
        return binaryFib(n-1) + binaryFib(n-2);
    }
    
    private static void fix(int [] arr, int index) {
        
        int temp;
        
        while((index > 0) && (arr[index - 1] < arr[index])) {
            temp = arr[index];
            arr[index] = arr[index-1];
            arr[index - 1] = temp;
            
            index--;
        }
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        
        int [] B = {10, 20, 30, 45, 50, 60, 80};
        System.out.println(binarySearch(B, 0, B.length - 1, 34));
        reverse(B);
        
        int [] C = {4, 4, 3, 3, 2, 2, 2, 1, 1};
        C[6] = 3;
        fix(C,6);
    }
}