/******************************************************************************
 * This program demonstrates a binary search.
 * 
 * Copyright © 2021 Richard Lesh.  All rights reserved.
 *****************************************************************************/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import org.pureprogrammer.Utils;

public class BinarySearch {

    static int binarySearch(final List<Integer> list, int value) {
        int left = 0;
        int right = list.size() - 1;
        while (left <= right) {
            final int m = (left + right) / 2;
            if (list.get(m) < value) {
                left = m + 1;
            } else if (list.get(m) > value) {
                right = m - 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    static int partition(List<Integer> list, int low, int high) {
        final int PIVOT = list.get((high + low) / 2);
        int i = low - 1;
        int j = high + 1;
        while (true) {
            do {
                ++i;
            } while (list.get(i) < PIVOT);
            do {
                --j;
            } while (list.get(j) > PIVOT);
            if (i >= j) {
                return j;
            }
            final int TEMP = list.get(j);
            list.set(j, list.get(i));
            list.set(i, TEMP);
        }
    }

    static void quicksort0(List<Integer> list, int low, int high) {
        if (low < high) {
            final int p = partition(list, low, high);
            quicksort0(list, low, p);
            quicksort0(list, p + 1, high);
        }
    }

    static void quicksort(List<Integer> list) {
        quicksort0(list, 0, list.size() - 1);
    }

    static long SEED = 3261963;
    static int lcgRand(long multiplier, long increment, long modulus) {
        SEED = (multiplier * SEED + increment) % modulus;
        return (int)(SEED & 0x7FFFFFFF);
    }

    public static void main(String[] args) {
        if (args.length != 1) {
            System.out.println(Utils.join("", "Syntax: ", "BinarySearch", " sample_size"));
            System.exit(1);
        }
        int sampleSize = Utils.stoiWithDefault(args[0], 10);

        List<Integer> samples = new ArrayList<>();
        System.out.println("Generating random integers...");
        long start = System.currentTimeMillis();
        for (int i = 0; i < sampleSize; ++i) {
            samples.add(lcgRand(0x19660D, 0x3C6EF35F, 4294967296L));
        }
        long stop = System.currentTimeMillis();
        System.out.println(Utils.format("Duration: {0:d} ms", stop - start));

        System.out.println("Sorting integers...");
        start = System.currentTimeMillis();
        quicksort(samples);
        stop = System.currentTimeMillis();
        System.out.println(Utils.format("Duration: {0:d} ms", stop - start));

        System.out.println("Searching integers...");
        start = System.currentTimeMillis();
        for (int i = 0; i < sampleSize; ++i) {
            final int POS = binarySearch(samples, samples.get(i));
        }
        stop = System.currentTimeMillis();
        System.out.println(Utils.format("Duration: {0:d} ms", stop - start));
    }
}