public class commonAlgorithm {

    /**
     * 判断一个数是否为素数
     *
     * @param num
     * @return
     */
    private static boolean isPrime(int num) {

        if (num <= 1) return false;
        if (num == 2) return true;
        if (num % 2 == 0) return false;

        for (int x = 3; x * x <= num; x += 2)
            if (num % x == 0)
                return false;

        return true;
    }

    // 计算arr[l...n)这个区间内所有数字的和
    private static int sum(int[] arr, int l) {
        if (l == arr.length)
            return 0;
        return arr[l] + sum(arr, l + 1);
    }

    /**
     * 交换数组元素
     *
     * @param arr
     * @param i
     * @param j
     */
    private static void swap(Object[] arr, int i, int j) {

        if (i < 0 || i >= arr.length)
            throw new IllegalArgumentException("i is out of bound.");

        if (j < 0 || j >= arr.length)
            throw new IllegalArgumentException("j is out of bound.");

        Object temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 求n的和
     *
     * @param n
     * @return
     */
    private static int sum(int n) {

        if (n < 0)
            throw new IllegalArgumentException("n should be greater or equal to zero.");

        int ret = 0;
        for (int i = 0; i <= n; i++)
            ret += i;
        return ret;
    }

    /**
     * 翻转数组
     *
     * @param arr
     */
    private static void reverse(Object[] arr) {

        int n = arr.length;
        for (int i = 0; i < n / 2; i++)
            swap(arr, i, n - 1 - i);
    }

    /**
     * 选择排序
     *
     * @param arr
     * @param n
     */
    private static void selectionSort(Comparable[] arr, int n) {

        for (int i = 0; i < n; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++)
                if (arr[j].compareTo(arr[minIndex]) < 0)
                    minIndex = j;

            swap(arr, i, minIndex);
        }
    }

    /**
     * 二分查找
     *
     * @param arr
     * @param n
     * @param target
     * @return
     */
    public static int binarySearch(Comparable[] arr, int n, Comparable target) {

        int l = 0, r = n; // 在[l...r)的范围里寻找target
        while (l < r) {    // 当 l == r 时, 区间[l...r)是一个无效区间
            int mid = l + (r - l) / 2;
            if (arr[mid].compareTo(target) == 0) return mid;
            if (target.compareTo(arr[mid]) > 0)
                l = mid + 1;  // target在[mid+1...r)中; [l...mid]一定没有target
            else    // target < arr[mid]
                r = mid;  // target在[l...mid)中; [mid...r)一定没有target
        }
        return -1;
    }


}