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; } }