Search Algorithms

Linear and binary are two search alogrithms, linear iterates over the array starting at the beginning searching for what you are looking for, O(n) is the time complexity. Binary search requires that the data be sorted, it chooses a element in the midlle of the array, if it matches the search is finished, if not then it compares if its greater than or less than and then it will search that side, it then search that half again, this repeats until the element is found, the time complexity is O(logn) as the array divides in half each time. The below diagram show how a binary search works

Below are some examples of linear and binary search algorithms.

Linear Search

package uk.co.datadisk.linearSearch;

public class LinearSearch {

  public static void main(String[] args) {

    int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };

    System.out.println("Index: " + linearSearch(intArray, -15));
    System.out.println("Index: " + linearSearch(intArray, -22));
    System.out.println("Index: " + linearSearch(intArray, 88));
  }

  public static int linearSearch(int[] input, int value){
    for (int i = 0; i < input.length; i++) {
      if(input[i] == value){
        return i;
      }
    }

    return -1;
  }
}

Binary Search

package uk.co.datadisk.binarySearch;

public class BinarySearch {

    public static void main(String[] args) {

        // ARRAY MUST BE SORTED !!!!!!
        int[] intArray = { -22, -15, 1, 7, 20, 35, 55 };

//        System.out.println(iterativeBinarySearch(intArray, -15));
//        System.out.println(iterativeBinarySearch(intArray, 35));
//        System.out.println(iterativeBinarySearch(intArray, 8888));
//        System.out.println(iterativeBinarySearch(intArray, 1));
//        System.out.println(iterativeBinarySearch(intArray, 55));
//        System.out.println(iterativeBinarySearch(intArray, -22));

        System.out.println(recursiveBinarySearch(intArray, -15));
        System.out.println(recursiveBinarySearch(intArray, 35));
        System.out.println(recursiveBinarySearch(intArray, 8888));
        System.out.println(recursiveBinarySearch(intArray, 1));
        System.out.println(recursiveBinarySearch(intArray, 55));
        System.out.println(recursiveBinarySearch(intArray, -22));
    }

    public static int iterativeBinarySearch(int[] input, int value){
        int start = 0;
        int end = input.length;

        while(start < end) {
            int midpoint = (start + end ) / 2;
            System.out.println("Midpoint (iterative) = " + midpoint);

            if(input[midpoint] == value){
                return midpoint;
            } else if(input[midpoint] < value) {
                start = midpoint + 1;
            } else {
                end = midpoint;
            }
        }
        return -1;
    }

    public static int recursiveBinarySearch(int[] input, int value) {
        return recursiveBinarySearch(input, 0, input.length, value);
    }

    private static int recursiveBinarySearch(int[] input, int start, int end, int value) {
        if (start >= end) {
            return -1;
        }

        int midpoint = (start + end ) / 2;
        System.out.println("Midpoint (recursive) = " + midpoint);

        if (input[midpoint] ==  value){
            return midpoint;
        } else if (input[midpoint] < value){
            return recursiveBinarySearch(input, midpoint +1, end, value);
        } else {
            return recursiveBinarySearch(input, start, midpoint, value);
        }
    }
}