public class LinearSearch {
// Iterative linear search — O(n)
static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i; // found at index i
}
return -1; // not found
}
// Recursive linear search — O(n)
static int linearSearchRec(int[] arr, int i, int target) {
if (i == arr.length) return -1; // base case: not found
if (arr[i] == target) return i; // base case: found
return linearSearchRec(arr, i + 1, target); // recursive case
}
// Find ALL occurrences
static void findAll(int[] arr, int target) {
boolean found = false;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
System.out.println("Found " + target + " at index " + i);
found = true;
}
}
if (!found) System.out.println(target + " not found");
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 1, 9, 2, 7, 4, 6};
System.out.println("Search 7: index " + linearSearch(arr, 7)); // 6
System.out.println("Search 10: index " + linearSearch(arr, 10)); // -1
System.out.println("Recursive search 9: index " +
linearSearchRec(arr, 0, 9)); // 4
int[] arr2 = {3, 1, 4, 1, 5, 9, 2, 6, 1};
findAll(arr2, 1); // Found at indices 1, 3, 8
}
}
/*
* Trace for arr = {5, 3, 8, 1, 9}, target = 9:
* i=0: arr[0]=5 ≠9
* i=1: arr[1]=3 ≠9
* i=2: arr[2]=8 ≠9
* i=3: arr[3]=1 ≠9
* i=4: arr[4]=9 = 9 → return 4
*/