Binary Search

Binary search or logarithmic search is a search algorithm to find a value within a sorted list. This algorithm compares the target value to the middle element of the array and if they are not equal the half in which the target cannot lie is eliminated and the search continues on the maining half. If the alforithm finished and the remaining half is empty, then the target value is not in the provided array.

This algorithm has the time complexity of O(log(n)) since it splits the search area by two every iteration.

Java

public static int binarySearch(ArrayList<Integer> array, int target) {
    new Quicksort().quicksort(array);

    int startIndex = 0;
    int endIndex = array.size() - 1;

    while (startIndex <= endIndex) {
        int centerIndex = (startIndex + endIndex) / 2;
        int centerValue = array.get(centerIndex);

        if (target == centerValue) {
            return centerIndex;
        } else if (target < centerValue) {
            endIndex = centerIndex - 1;
        } else {
            startIndex = centerIndex + 1;
        }
    }

    return -1;
}