Linear search is a rather slow but easy searching method. You have the array and the element to find, so you check all the elements from the first to the last. If you find the element, you return TRUE or the index to the caller. If you arrived at the end of the cycle, the element is not present.

Obviously, the complexity of this algorithm strongly depends on the presence (or absence) of the element and on its position. In fact, in the worst case (element not present or present at the last index) the complexity is O(n), while in the better case (element at the first position) it's O(1).

So the average complexity is considered: O(N/2). It's easy to understand why it's not the better choice for big arrays and/or if you need to compute a large number of searches.

Here an implementation of a recursive linear search. I'm sure recursion here isn't the best choice, but the iterative version was banal!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

import java.util.Arrays; public class RecursiveLinearSearch { public static void main(String[] args) { int[] v1 = {1, 4, 5, 6}; int[] elements = {1, 7}; System.out.println("Array is: " + Arrays.toString(v1)); for (int i = 0; i < elements.length; i++) { System.out.println("Searching element " + elements[i] + " returned " + recursiveLinearSearch(v1, elements[i], 0)); } } /* * Instead of returning the index, I'm returning a boolean value * but it's basically the same thing * (you can use start as an index and -1 as a "not found" value */ public static boolean recursiveLinearSearch(int[] V, int num, int start) { if (start == V.length) { return false; } if (V[start] == num) { return true; } return recursiveLinearSearch(V, num, start+1); } }