binsearch.java

package binsearch;

import javafx.util.Pair;

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

/**
 * Created by max on 15.09.15.
 */
public class Main {
    public static int binarySearchRecursive(final Integer[] data, final int value, final int top, final int bot) {
        if (bot > top) {
            return -1;
        }

        final int pos = (top + bot) / 2;
        final int data_val = data[pos];

        if (data_val > value) {
            return binarySearchRecursive(data, value, pos - 1, bot);
        }

        if (data_val < value) {
            return binarySearchRecursive(data, value, top, pos + 1);
        }

        Thread.dumpStack();
        return pos;
    }

    public static int binarySearchIterative(final Integer[] data, final int value, int top, int bot) {
        int pos;
        int data_val;

        while (bot <= top) {
            pos = (top + bot) / 2;
            data_val = data[pos];

            if (data_val == value) {
                Thread.dumpStack();
                return pos;
            }

            if (data_val > value) {
                top = pos - 1;
                continue;
            }

            if (data_val < value) {
                bot = pos + 1;
            }
        }

        return -1;
    }

    public static int binarySearchOrNextStackBased(final Integer[] data, final int value, int top, int bot) {
        int pos;
        int data_val;
        final Stack<Pair<Integer, Integer>> stack = new Stack<>();

        while (true) {
            pos = (top + bot) / 2;
            data_val = data[pos];

            stack.add(new Pair<>(pos, data_val));

            if (data_val == value) {
                Thread.dumpStack();
                return pos;
            }

            if (data_val > value) {
                top = pos - 1;
                continue;
            }

            if (data_val < value) {
                bot = pos + 1;
            }

            if (bot > top) {
                while (!stack.isEmpty()) {
                    Pair<Integer, Integer> pair = stack.pop();
                    int oPos = pair.getKey();
                    int oVal = pair.getValue();

                    if (oVal < value) {
                        continue;
                    }

                    Thread.dumpStack();
                    return oPos;
                }

                return -1;
            }
        }
    }

    public static void main(String[] args) {
        final Random random = new Random();
        final Integer data[] = new Integer[10];
        final int MAX_VALUE = 454;

        for (int i = 0; i < data.length; i++) {
            data[i] = Math.abs(random.nextInt() % MAX_VALUE);
        }

        Arrays.sort(data);

        StringBuilder stringBuilder = new StringBuilder();

        final int VALUE_TO_SEARCH = data[Math.abs(random.nextInt() % data.length)] ;

        stringBuilder.append("Value to look up: " + VALUE_TO_SEARCH + '\n');
        stringBuilder.append(Arrays.toString(data) + '\n');
        stringBuilder.append("(binarySearchIterative) Found at index " + binarySearchIterative(data, VALUE_TO_SEARCH, data.length - 1, 0) + '\n');
        stringBuilder.append("(binarySearchRecursive) Found at index " + binarySearchRecursive(data, VALUE_TO_SEARCH, data.length - 1, 0) + '\n');
        stringBuilder.append("(binarySearchOrNextStackBased) Found at index " + binarySearchOrNextStackBased(data, VALUE_TO_SEARCH, data.length - 1, 0) + '\n');

        System.out.println(stringBuilder.toString());
    }
}