/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package sdp_algorithm;

import java.util.Arrays;

/**
 *
 * @author azeez taiwo
 * @company iQubeLabs
 * @date 23/07/2016
 *
 */
public class SearchAlgorithms {

    /**
     * binary search, also known as half-interval search or logarithmic search
     * is a search algorithm that finds the position of a target value
     * within a sorted array.It compares the target value to the middle element of the array;
     * if they are unequal, the half in which the target cannot lie is
     * eliminated and the search continues on the remaining half until it is successful.
     *
     * Worst time complexity of 0(logN)
     * Best time complexity of 0(1)
     *
     * For more information, check out https://en.wikipedia.org/wiki/Binary_search_algorithm
     *
     * @param a array of integer elements
     * @param x value to search for
     * @return the index of the element that equals x or -1 incase no match was found
     */
    static int binarySearch(int[] a, int x) {
        Arrays.sort(a);
        return binarySearchHelper(a, 0, a.length - 1, x);
    }
    public static void main(String[] args) {
        int[] x = {9,5,6,2,11,6,8,7,112};
        System.out.println(interpolationSearch(x, 6));
        System.out.println(binarySearch(x, 6));
        System.out.println(linearSearch(x, 6));

    }

    static int binarySearchHelper(int[] a, int l, int h, int x) {
        if (l > h) {
            return -1;
        } else {
            int m = (l + h) / 2;
            if (a[m] == x) {
                return m;
            } else if (a[m] < x) {
                return binarySearchHelper(a, m + 1, h, x);
            }
            return binarySearchHelper(a, l, m - 1, x);
        }
    }



    /**This method sequentially checks each element of the array
     * until a match is found.
     *
     * Best case performace of O(1)
     * Worst case performance of O(N).
     *
     * For more information, check out https://en.wikipedia.org/wiki/Linear_search
     *
     * @param a array of integer elements
     * @param x value to search for
     * @return the index of the element that equals x or -1 incase no match was found
     */
    static int linearSearch(int[] a, int x) {
        for (int i = 0; i < a.length; ++i) {
            if (a[i] == x) {
                return i;
            }
        }
        return -1;
    }

    /**This algorithm searches for a given key value in an indexed array that has
     * been ordered by the values of the key
     *
     * Average runtime complexity for uniformly distributed elements of O(log(logN))
     * Worst case complexity of 0(N)
     *
     *  For more information, check out https://en.wikipedia.org/wiki/Interpolation_search
     *
     * @param a array of integer elements
     * @param x value to search for
     * @return the index of the element that equals x or -1 incase no match was found
     */
    static int interpolationSearch(int[] a, int x) {
        Arrays.sort(a);
        int h = a.length - 1;
        int l = 0;

        while (a[h] >= x && a[l] < x) {
            int num = h - l;
            int denom = a[h] - a[l];
            int i = (num / denom)    * x + l;
            if (a[i] < x) {
                l = i + 1;
            } else if (a[i] > x) {
                h = i - 1;
            } else {
                l = i;
            }
        }
        if (a[l] == x) {
            return l;
        }
        return -1;
    }
}