2. Searching

When we want to find an index (or -1 if not found) of an element, we must search the array using an algorithm. Implementations will include both iterative and recursive solutions.

Linear Search

Linear search is the easiest of all searches as it sequentially checks each element to find the first occurrence and returns that index. Linear search has a time complexity of $O(n)$ as we are sequentially searching elements.

Array

public <T extends Comparable<? super T>> int linearSearch(T[] array, T element) {
    for (int i = 0; i < array.length; i++) {
        if (array[i].compareTo(element) == 0) {
            return i;
        }
    }
    return -1;
}

public <T extends Comparable<? super T>> int linearSearch(T[] array, T element) {
    return linearSearchHelper(array, array.length, element);
}

private <T extends Comparable<? super T>> int linearSearchHelper(T[] array, int size, T element) {
    if (size == 0) {
        return -1;
    }
    if (array[size - 1].compareTo(element) == 0) {
        return size - 1;
    }
    return linearSearchHelper(arrray, size - 1, key);
}

Linked List

public <T extends Comparable<? super T>> int linearSearch(Node<T> head, T element) {
    Node<T> curr = head;
    int i = 0;

    while(curr != null) {
        if (curr.data.CompareTo(element) == 0) {
            return i;
        }
        i++;
        curr = curr.next;
    }

    return -1;
}

public <T extends Comparable<? super T>> int linearSearch(Node<T> head, T element) {
    return linearSearchHelper(head, 0, element)
}

private <T extends Comparable<? super T>> int linearSearchHelper(Node<T> curr, int index, T element) {
    if (curr == null) {
        return -1;
    }
    if (curr.data.compareTo(element) == 0) {
        return index;
    }

    return linearSearchHelper(curr.next, index + 1, element);
}

Binary Search

Binary search is a divide and conquer algorithm where it repeating splits the array in halfs until it finds the element it is attempting to find. This algorithm does not always find the first occurrence of an element, but it does run in $O(log(n))$ time because it divides and conquers. This algorithm only works when the data is sorted, and it can not work on linked-lists (remember linked-list have get time of $O(n)$ while arrays have get time of $O(1)$).

public <T extends Comparable<? super T>> int binarySearch(T[] array, T element) {
    int low = 0;
    int high = array.length;

    while(high >= low) {
        int middle = Math.floorDiv(low + high, 2);
        if (array[middle].compareTo(element) == 0) {
            return middle;
        } else if (array[middle].compareTo(element) < 0) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }

    return -1;
}

public <T extends Comparable<? super T>> int binarySearch(T[] array, T element) {
    return binarySearchHelper(array, element, 0, array.length);
}

private <T extends Comparable<? super T>> int binarySearchHelper(T[] array, T element, int low, int high) {
    if (high >= low) {
        int middle = Math.floorDiv(low + high, 2);
        if (array[middle].compareTo(element) == 0) {
            return middle;
        } else if (array[middle].compareTo(element) < 0) {
            return binarySearchHelper(array, element, middle + 1, high);
        } else {
            return binarySearchHelper(array, element, low, middle - 1);
        }
    }

    return -1;
}

Ok, so how do we sort an array now? Well... there are some options.

Next Page →