package jawa;

import java.util.Arrays;

public class jabba {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int [] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.println(binarySearch(arr, 9));
        System.out.println(recursiveBinary(arr, 9));
        int [] unsort = {1, 22, 10, 4, 5, 3, 5, 8, 2};
        int [] unsort2 = {1, 22, 10, 3, 5, 8, 5, 12, 2};
        bubbleSort(unsort);
        insertionSort(unsort2);
        System.out.println(Arrays.toString(unsort));
        System.out.println(Arrays.toString(unsort2));
    }

    public static int linearSearch(int[] arr, int target){
        for (int i = 0; i < arr.length; i++){
            if (arr[i] == target){
                return i;
            }

        }
        return -1;
    }

    public static int binarySearch(int[] arr, int target){
        int low = 0;
        int high = arr.length-1;
        boolean cont = true;
        int guess = (low+high)/2;
        while (cont){

            if (arr[guess] == target){
                return guess;
            }
            else if (arr[guess] > target) {
                high = guess - 1;
                guess = (low+high)/2;
            }

            else if (arr[guess] < target) {
                low = guess + 1;
                guess = (low+high)/2;
            }
            if (high < low){
                return -1;
            }
        }
        return -1;

    }

    public static int recursiveBinarySearch(int[] arr, int target, int low, int high){
        if (low > high){
            return -1;
        }
        if (arr[(low+high)/2] == target){
            return (low+high)/2;
        }
        else if (target < arr[(low+high)/2]){
            return recursiveBinarySearch(arr, target, low, ((low+high)/2)-1 );
        }
        else if (target > arr[(low+high)/2]){
            return recursiveBinarySearch(arr, target, ((low+high)/2)+1, high );
        }
        else
            return -1;
    }

    public static int recursiveBinary(int[] arr, int target){
        return recursiveBinarySearch(arr, target, 0, arr.length-1);
    }

    public static void bubbleSort(int[] input){

        boolean hasSwapped = false;
        do {
            hasSwapped = false;
            for (int i = 0; i < input.length-1; i++){

                if (input[i] > input[i+1]){
                    int temp = input[i];
                    input[i] = input[i+1];
                    input[i+1] = temp;
                    hasSwapped = true;
                }
            }
        }while (hasSwapped);
    }

    public static void insertionSort(int[] arr){
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;


            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void selectionSort(int arr[])
    {
        int n = arr.length;


        for (int i = 0; i < n-1; i++)
        {

            int min_idx = i;
            for (int j = i+1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;


            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
}