Бинарный поиск

Одним из основных алгоритмов поиска является бинарный поиск. Он работает только с отсортированными данными, за счет этого достигается большая скорость поиска: O(logN). Принцип работы алгоритма прост: находим середину массива данных, проверяем, больше, меньше и равно искомое значение значению в середине. Если равно, значит нашли. Если искомое больше, значит дальше ищем только в правой половине, если меньше - в левой. Т.е. с каждой итерацией количество данных для поиска делится надвое.

public class Binary {
    public static void main(String[] args) {
        int[] arr = { 1,12,23,34,55,61,67,88,89,101 };
        System.out.println(rank(55, arr));
    }
    
    public static int rank(int val, int[] arr) {
        return rank(val, arr, 0, arr.length-1);
    }
    
    private static int rank(int val, int[] arr, int lo, int hi) {
        if (lo > hi) return -1;
        
        int mid = lo + (hi - lo) / 2;
        
        if (val < arr[mid]) {
            return rank(val, arr, lo, mid - 1);
        } else if (val > arr[mid]) {
            return rank(val, arr, mid + 1, hi);
        } else {
            return mid;
        }
    }
}

Как проверить, является ли число простым

Простые числа являются элементарными строительными блоками натуральных чисел. Простые числа применяются, например, в криптографии. За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр назначена премия в 150 000 и 250 000 долларов США, говорится в Википедии.

/**
 * Является ли число простым?
 */
public static boolean isPrime(int N) {
    if (N < 2) return false;
    for (int i = 2; i*i <= N; i++)
        if (N % i == 0) return false;
    return true;
}

Умножение матриц

Умножение матриц - одна из основных операций над матрицами. Принцип умножения матриц хорошо описан в Википедии

В двумерном массиве arr[m][n], по соглашению, первое значение - количество строк, второе - столбцов.

Применение умножения матриц можно найти, например,при программировании поведения объектов в трехмерном пространстве.

public class MatrixMultiplection {
    public static void main(String[] args) {
        int[][] mA = 
            {{33,34,12},
             {33,19,10},
             {12,14,17},
             {84,24,51},
             {43,71,21}};
        
        int[][] mB = 
            {{10,11,34,55},
             {33,45,17,81},
             {45,63,12,16}};

        
        int m = mA.length;
        int n = mB[0].length;
        int o = mB.length;
        int[][] res = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < o; k++) {
                    res[i][j] += mA[i][k] * mB[k][j]; 
                }
            }
        }
        
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[0].length; j++) {
                System.out.format("%6d ", res[i][j]);
            }
            System.out.println();
        }
    }
}
/**
  Output:   
  1992   2649   1844   4761 
  1407   1848   1565   3514 
  1347   1833    850   2066 
  3927   5217   3876   7380 
  3718   4991   2921   8452
 */

Данный алгоритм имеет сложность O(n³). Алгоритм Копперсмита — Винограда может делать это за O(n^2.3727).

Выстраиваем элементы массива в обратном порядке

import java.util.Arrays;
/**
 * Меняет порядок элементов массива на обратный за n/2
 */
public class ReverseElements {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10,11};
        for (int i = 0; arr.length/2 > i; i++) {
            int tmp = arr[i];
            arr[i] = arr[arr.length - i - 1];
            arr[arr.length - i - 1] = tmp;
        }
        System.out.println(Arrays.toString(arr));
        
    }
}

Наибольший общий делитель

/**
 * Алгоритм Евклида. Наибольший общий делитель
 * */
public class GratestCommonDivisor {
    public static void main(String[] args) {
        System.out.println(gcd(30000, 1701));
    }
    
    public static int gcd(int a, int b) {
        if (b == 0) return a;
        int x = a % b;
        return gcd(b, x);
    }
}