2017b

Версия 09:55, 2 апреля 2015

Бинарный поиск (в массиве)

import java.util.Arrays;
import java.util.Random;


public class Main {

        public static void main(String[] args) {
                int[] arr = new int[100];
                
                Random r = new Random();
                for (int i = 0; i < arr.length; i++) {
                        arr[i] = r.nextInt(20);
                }
                Arrays.sort(arr);
                
                int x = 12;
                
                int beg = 0;
                int end = arr.length;
                int flag = -1;
                
                while (beg != end) {
                        int m = (beg+end)/2;
                        if (arr[m] == x) {
                                flag = m;
                                break;
                        }
                        if (arr[m] > x) {
                                end = m;
                        } else {
                                beg = m + 1;
                        }
                }
                
                System.out.println(flag);
        }

}

Бинарный поиск (корень энной степени)

public class Main2 {

        public static void main(String[] args) {
                int n = 2;
                int a = 9;
                
                double beg = 0;
                double end = a+1;
                double flag = -1;
                double m = 0;
                
                while (end-beg >= 1e-15) {
                        m = (beg+end)/2;
                        double t = Math.pow(m, n); 
                        if (t == a) {
                                flag = m;
                                break;
                        }
                        if (t > a) {
                                end = m;
                        } else {
                                beg = m;
                        }
                }
                
                System.out.println(m);
        }

}

НОД и время работы

import java.util.Random;

public class Main {
        public static int gcd1(int a, int b) {
                if (a * b == 0) {
                        return a + b;
                }
                if (a > b) {
                        return gcd1(a % b, b);
                }
                return gcd1(a, b % a);
        }

        public static int gcd2(int a, int b) {
                while (a * b != 0) {
                        if (a > b) {
                                a = a % b;
                        } else {
                                b = b % a;
                        }
                }
                return a + b;
        }

        public static int gcd3(int a, int b) {
                while (a * b != 0) {
                        if (a > b) {
                                a = a - b;
                        } else {
                                b = b - a;
                        }
                }
                return a + b;
        }

        public static void main(String[] args) {
                Random r = new Random();

                long t = System.currentTimeMillis();

                for (int i = 0; i < 10000000; i++) {
                        int a = r.nextInt(2000000000);
                        int b = r.nextInt(2000000000);
                        int c = gcd1(a, b);
                }

                System.out.println(System.currentTimeMillis() - t);
                
        }
}