Linear Search - Java Programming

When searching through a small collection like a shopping cart or a list of recent notifications, you need a simple and reliable method. Linear search checks each item one by one, making it useful for unsorted data and small datasets where more complex algorithms are unnecessary.

Basic Implementation

Linear search compares each element with a target until it finds a match or reaches the end.

                            target
                            target = 8 (default)target = 1target = 7
                        

                            Basic.java
                        
Replay: real traced execution (multi-file project)

                            public class Basic {
    static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;  // found - return index
            }
        }
        return -1;  // not found
    }

    public static void main(String[] args) {
        int[] numbers = {5, 2, 8, 1, 9, 3};
        int target = 8;

        System.out.println("Array: " + java.util.Arrays.toString(numbers));
        System.out.println("Search " + target + ": index " + linearSearch(numbers, target));
    }
}
public class Basic {
    static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;  // found - return index
            }
        }
        return -1;  // not found
    }

    public static void main(String[] args) {
        int[] numbers = {5, 2, 8, 1, 9, 3};
        int target = 1;

        System.out.println("Array: " + java.util.Arrays.toString(numbers));
        System.out.println("Search " + target + ": index " + linearSearch(numbers, target));
    }
}
public class Basic {
    static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;  // found - return index
            }
        }
        return -1;  // not found
    }

    public static void main(String[] args) {
        int[] numbers = {5, 2, 8, 1, 9, 3};
        int target = 7;

        System.out.println("Array: " + java.util.Arrays.toString(numbers));
        System.out.println("Search " + target + ": index " + linearSearch(numbers, target));
    }
}

                        
1target ← 8⋯11public static void main(String[] args) {12    int[] numbers = {5, 2, 8, 1, 9, 3};13    int target→ 8 = 8; //@target=8, 1, 714    15    System.out.println("Array: " + java.util.Arrays.toString(numbers));16    System.out.println("Search " + target8 + ": index " + linearSearch(numbers, target));17}⋯outputArray: [5, 2, 8, 1, 9, 3]
2static int linearSearch(int[] arr, int target)1public class Basic {2    static int linearSearch(int[] arr, int target8) {3        for (int i = 0; i < arr.length; i++) {⋯
3for (int i = 0; i < arr.length; i++)pass 1 of 3⋯2static int linearSearch(int[] arr, int target) {3    for (int i0 = 0; i < arr.length6; i++) {4        if (arr[i] == target) {⋯All 3 passes — pass 1 is the card abovepassiarr[i]target
10——
21——
3288
4if (arr[i] == target)⋯3for (int i = 0; i < arr.length; i++) {4    if (arr[i]8 == target8) {5        return i2;  // found - return index6    }⋯
5System.out.println("Search " + target + ": index " + linearSearch(numb…⋯15    System.out.println("Array: " + java.util.Arrays.toString(numbers));16    System.out.println("Search " + target8 + ": index " + linearSearch(numbers, target));17}⋯outputSearch 8: index 2
1target ← 1⋯11public static void main(String[] args) {12    int[] numbers = {5, 2, 8, 1, 9, 3};13    int target→ 1 = 1;14    15    System.out.println("Array: " + java.util.Arrays.toString(numbers));16    System.out.println("Search " + target1 + ": index " + linearSearch(numbers, target));17}⋯outputArray: [5, 2, 8, 1, 9, 3]
2static int linearSearch(int[] arr, int target)1public class Basic {2    static int linearSearch(int[] arr, int target1) {3        for (int i = 0; i < arr.length; i++) {⋯
3for (int i = 0; i < arr.length; i++)pass 1 of 4⋯2static int linearSearch(int[] arr, int target) {3    for (int i0 = 0; i < arr.length6; i++) {4        if (arr[i] == target) {⋯All 4 passes — pass 1 is the card abovepassiarr[i]target
10——
21——
32——
4311
4if (arr[i] == target)⋯3for (int i = 0; i < arr.length; i++) {4    if (arr[i]1 == target1) {5        return i3;  // found - return index6    }⋯
5System.out.println("Search " + target + ": index " + linearSearch(numb…⋯15    System.out.println("Array: " + java.util.Arrays.toString(numbers));16    System.out.println("Search " + target1 + ": index " + linearSearch(numbers, target));17}⋯outputSearch 1: index 3
1target ← 7⋯11public static void main(String[] args) {12    int[] numbers = {5, 2, 8, 1, 9, 3};13    int target→ 7 = 7;14    15    System.out.println("Array: " + java.util.Arrays.toString(numbers));16    System.out.println("Search " + target7 + ": index " + linearSearch(numbers, target));17}⋯outputArray: [5, 2, 8, 1, 9, 3]
2static int linearSearch(int[] arr, int target)1public class Basic {2    static int linearSearch(int[] arr, int target7) {3        for (int i = 0; i < arr.length; i++) {⋯
3for (int i = 0; i < arr.length; i++)pass 1 of 6⋯2static int linearSearch(int[] arr, int target) {3    for (int i0 = 0; i < arr.length6; i++) {4        if (arr[i] == target) {⋯All 6 passes — pass 1 is the card abovepassi
10
21
32
43
54
65
4return -1;  // not found⋯7    }8    return -1;  // not found9}⋯
5System.out.println("Search " + target + ": index " + linearSearch(numb…⋯15    System.out.println("Array: " + java.util.Arrays.toString(numbers));16    System.out.println("Search " + target7 + ": index " + linearSearch(numbers, target));17}⋯outputSearch 7: index -1

All 3 passes — pass 1 is the card above
pass	`i`	`arr[i]`	`target`
1	0	—	—
2	1	—	—
3	2	8	8

All 4 passes — pass 1 is the card above
pass	`i`	`arr[i]`	`target`
1	0	—	—
2	1	—	—
3	2	—	—
4	3	1	1

All 6 passes — pass 1 is the card above
pass	`i`
1	0
2	1
3	2
4	3
5	4
6	5

Linear Search A sequential search algorithm that examines each element in order until finding the target or exhausting all elements.

Searching Strings

The same algorithm works for object values when the equality check matches the data type.

                            Strings.java
                        
Replay: real traced execution (multi-file project)

                            public class Strings {
    static int searchString(String[] arr, String target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].equals(target)) {
                return i;
            }
        }
        return -1;
    }

    static int searchCaseInsensitive(String[] arr, String target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].equalsIgnoreCase(target)) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String[] fruits = {"apple", "banana", "cherry", "date", "elderberry"};

        System.out.println("Fruits: " + java.util.Arrays.toString(fruits));
        System.out.println("Search 'cherry': " + searchString(fruits, "cherry"));
        System.out.println("Search 'grape': " + searchString(fruits, "grape"));

        System.out.println("\nCase-insensitive:");
        System.out.println("Search 'BANANA': " + searchCaseInsensitive(fruits, "BANANA"));
        System.out.println("Search 'Apple': " + searchCaseInsensitive(fruits, "Apple"));
    }
}

                        
1public static void main(String[] args)⋯20public static void main(String[] args) {21    String[] fruits = {"apple", "banana", "cherry", "date", "elderberry"};22    23    System.out.println("Fruits: " + java.util.Arrays.toString(fruits));24    System.out.println("Search 'cherry': " + searchString(fruits, "cherry"));25    System.out.println("Search 'grape': " + searchString(fruits, "grape"));⋯outputFruits: [apple, banana, cherry, date, elderberry]
2static int searchString(String[] arr, String target)pass 1 of 21public class Strings {2    static int searchString(String[] arr, String targetcherry) {3        for (int i = 0; i < arr.length; i++) {⋯
3for (int i = 0; i < arr.length; i++)pass 1 of 8⋯2static int searchString(String[] arr, String target) {3    for (int i0 = 0; i < arr.length5; i++) {4        if (arr[i].equals(target)) {⋯All 8 passes — pass 1 is the card abovepassiarr[i]target
10——
21——
32cherrycherry
40——
51——
62——
73——
84——
4if (arr[i].equals(target))⋯3for (int i = 0; i < arr.length; i++) {4    if (arr[i]cherry.equals(targetcherry)) {5        return i2;6    }⋯
5System.out.println("Search 'cherry': " + searchString(fruits, "cherry"…⋯23System.out.println("Fruits: " + java.util.Arrays.toString(fruits));24System.out.println("Search 'cherry': " + searchString(fruits, "cherry"));25System.out.println("Search 'grape': " + searchString(fruits, "grape"));⋯outputSearch 'cherry': 2
6static int searchString(String[] arr, String target)pass 2 of 21public class Strings {2    static int searchString(String[] arr, String targetgrape) {3        for (int i = 0; i < arr.length; i++) {⋯
7return -1;⋯7    }8    return -1;9}⋯
8System.out.println("Search 'grape': " + searchString(fruits, "grape"))…⋯24System.out.println("Search 'cherry': " + searchString(fruits, "cherry"));25System.out.println("Search 'grape': " + searchString(fruits, "grape"));2627System.out.println("\nCase-insensitive:");28System.out.println("Search 'BANANA': " + searchCaseInsensitive(fruits, "BANANA"));29System.out.println("Search 'Apple': " + searchCaseInsensitive(fruits, "Apple"));⋯outputSearch 'grape': -1

Case-insensitive:
9static int searchCaseInsensitive(String[] arr, String target)pass 1 of 2⋯11static int searchCaseInsensitive(String[] arr, String targetBANANA) {12    for (int i = 0; i < arr.length; i++) {⋯
10for (int i = 0; i < arr.length; i++)pass 1 of 3⋯11static int searchCaseInsensitive(String[] arr, String target) {12    for (int i0 = 0; i < arr.length5; i++) {13        if (arr[i].equalsIgnoreCase(target)) {⋯All 3 passes — pass 1 is the card abovepassiarr[i]target
10——
21bananaBANANA
30appleApple
11if (arr[i].equalsIgnoreCase(target))pass 1 of 2⋯12for (int i = 0; i < arr.length; i++) {13    if (arr[i]banana.equalsIgnoreCase(targetBANANA)) {14        return i1;15    }⋯
12System.out.println("Search 'BANANA': " + searchCaseInsensitive(fruits,…⋯27    System.out.println("\nCase-insensitive:");28    System.out.println("Search 'BANANA': " + searchCaseInsensitive(fruits, "BANANA"));29    System.out.println("Search 'Apple': " + searchCaseInsensitive(fruits, "Apple"));30}⋯outputSearch 'BANANA': 1
13static int searchCaseInsensitive(String[] arr, String target)pass 2 of 2⋯11static int searchCaseInsensitive(String[] arr, String targetApple) {12    for (int i = 0; i < arr.length; i++) {⋯
14if (arr[i].equalsIgnoreCase(target))pass 2 of 2⋯12for (int i = 0; i < arr.length; i++) {13    if (arr[i]apple.equalsIgnoreCase(targetApple)) {14        return i0;15    }⋯
15System.out.println("Search 'Apple': " + searchCaseInsensitive(fruits, …⋯28    System.out.println("Search 'BANANA': " + searchCaseInsensitive(fruits, "BANANA"));29    System.out.println("Search 'Apple': " + searchCaseInsensitive(fruits, "Apple"));30}⋯outputSearch 'Apple': 0

All 8 passes — pass 1 is the card above
pass	`i`	`arr[i]`	`target`
1	0	—	—
2	1	—	—
3	2	cherry	cherry
4	0	—	—
5	1	—	—
6	2	—	—
7	3	—	—
8	4	—	—

All 3 passes — pass 1 is the card above
pass	`i`	`arr[i]`	`target`
1	0	—	—
2	1	banana	BANANA
3	0	apple	Apple

Counting Occurrences

Linear search can track work done while it scans.

                            Count.java
                        
Replay: real traced execution (multi-file project)

                            public class Count {
    static class SearchResult {
        int index;
        int comparisons;

        SearchResult(int index, int comparisons) {
            this.index = index;
            this.comparisons = comparisons;
        }
    }

    static SearchResult linearSearchCounted(int[] arr, int target) {
        int comparisons = 0;
        for (int i = 0; i < arr.length; i++) {
            comparisons++;
            if (arr[i] == target) {
                return new SearchResult(i, comparisons);
            }
        }
        return new SearchResult(-1, comparisons);
    }

    public static void main(String[] args) {
        int[] numbers = {10, 20, 30, 40, 50};

        var result1 = linearSearchCounted(numbers, 10);  // first element
        System.out.println("Search 10: index=" + result1.index +
                         ", comparisons=" + result1.comparisons);

        var result2 = linearSearchCounted(numbers, 50);  // last element
        System.out.println("Search 50: index=" + result2.index +
                         ", comparisons=" + result2.comparisons);

        var result3 = linearSearchCounted(numbers, 99);  // not found
        System.out.println("Search 99: index=" + result3.index +
                         ", comparisons=" + result3.comparisons);
    }
}

                        
1public static void main(String[] args)⋯23public static void main(String[] args) {24    int[] numbers = {10, 20, 30, 40, 50};25    26    var result1 = linearSearchCounted(numbers, 10);  // first element27    System.out.println("Search 10: index=" + result1.index + ⋯
2comparisons ← 0pass 1 of 3⋯12static SearchResult linearSearchCounted(int[] arr, int target10) {13    int comparisons→ 0 = 0;14    for (int i = 0; i < arr.length; i++) {⋯All 3 passes — pass 1 is the card abovepasstargetarr[i]icomparisons
1101000
2505040
399——0
3comparisons ← 1pass 1 of 11⋯13int comparisons = 0;14for (int i0 = 0; i < arr.length5; i++) {15    comparisons→ 1++;16    if (arr[i] == target) {⋯All 11 passes — pass 1 is the card abovepassiarr[i]targetcomparisons
1010100 → 1
20——0 → 1
31——1 → 2
42——2 → 3
53——3 → 4
6450504 → 5
70——0 → 1
81——1 → 2
92——2 → 3
103——3 → 4
114——4 → 5
4if (arr[i] == target)pass 1 of 2⋯15comparisons++;16if (arr[i]10 == target10) {17    return new SearchResult(i, comparisons);18}⋯values this step0i
5this.index ← 0, this.comparisons ← 1pass 1 of 3⋯6SearchResult(int index0, int comparisons1) {7    this.index→ 0 = index0;8    this.comparisons→ 1 = comparisons1;9}⋯All 3 passes — pass 1 is the card abovepassindexcomparisonsthis.indexthis.comparisons
10101
24545
3-15-15
6result1 ← ⟨Count$SearchResult A⟩⋯26var result1→ ⟨Count$SearchResult A⟩ = linearSearchCounted(numbers, 10);  // first element27System.out.println("Search 10: index=" + result1.index0 + 28                 ", comparisons=" + result1.comparisons1);2930var result2 = linearSearchCounted(numbers, 50);  // last element31System.out.println("Search 50: index=" + result2.index + ⋯outputSearch 10: index=0, comparisons=1
7if (arr[i] == target)pass 2 of 2⋯15comparisons++;16if (arr[i]50 == target50) {17    return new SearchResult(i, comparisons);18}⋯values this step4i
8result2 ← ⟨Count$SearchResult B⟩⋯30var result2→ ⟨Count$SearchResult B⟩ = linearSearchCounted(numbers, 50);  // last element31System.out.println("Search 50: index=" + result2.index4 + 32                 ", comparisons=" + result2.comparisons5);3334var result3 = linearSearchCounted(numbers, 99);  // not found35System.out.println("Search 99: index=" + result3.index + ⋯outputSearch 50: index=4, comparisons=5
9return new SearchResult(-1, comparisons);⋯19    }20    return new SearchResult(-1, comparisons);21}⋯
10result3 ← ⟨Count$SearchResult C⟩⋯34    var result3→ ⟨Count$SearchResult C⟩ = linearSearchCounted(numbers, 99);  // not found35    System.out.println("Search 99: index=" + result3.index-1 + 36                     ", comparisons=" + result3.comparisons5);37}⋯outputSearch 99: index=-1, comparisons=5

All 3 passes — pass 1 is the card above
pass	`target`	`arr[i]`	`i`
1	10	10	0
2	50	50	4
3	99	—	—

All 11 passes — pass 1 is the card above
pass	`i`	`arr[i]`	`target`	`comparisons`
1	0	10	10	0 → 1
2	0	—	—	0 → 1
3	1	—	—	1 → 2
4	2	—	—	2 → 3
5	3	—	—	3 → 4
6	4	50	50	4 → 5
7	0	—	—	0 → 1
8	1	—	—	1 → 2
9	2	—	—	2 → 3
10	3	—	—	3 → 4
11	4	—	—	4 → 5

All 3 passes — pass 1 is the card above
pass	`index`	`comparisons`	`this.index`	`this.comparisons`
1	0	1	0	1
2	4	5	4	5
3	-1	5	-1	5

Finding All Matches

Instead of stopping at the first match, keep scanning and collect every matching index.

                            FindAll.java
                        
Replay: real traced execution (multi-file project)

                            import java.util.ArrayList;
import java.util.List;

public class FindAll {
    static List<Integer> findAll(int[] arr, int target) {
        List<Integer> indices = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                indices.add(i);
            }
        }
        return indices;
    }

    public static void main(String[] args) {
        int[] numbers = {3, 7, 3, 9, 3, 1, 3};

        System.out.println("Array: " + java.util.Arrays.toString(numbers));
        System.out.println("All 3's at: " + findAll(numbers, 3));
        System.out.println("All 9's at: " + findAll(numbers, 9));
        System.out.println("All 5's at: " + findAll(numbers, 5));
    }
}

                        
1public static void main(String[] args)⋯15public static void main(String[] args) {16    int[] numbers = {3, 7, 3, 9, 3, 1, 3};17    18    System.out.println("Array: " + java.util.Arrays.toString(numbers));19    System.out.println("All 3's at: " + findAll(numbers, 3));20    System.out.println("All 9's at: " + findAll(numbers, 9));⋯outputArray: [3, 7, 3, 9, 3, 1, 3]
2indices ← []pass 1 of 3⋯4public class FindAll {5    static List<Integer> findAll(int[] arr, int target3) {6        List<Integer> indices→ [] = new ArrayList<>();7        for (int i = 0; i < arr.length; i++) {⋯All 3 passes — pass 1 is the card abovepasstargetindices
13[]
29[]
35[]
3for (int i = 0; i < arr.length; i++)pass 1 of 21⋯6List<Integer> indices = new ArrayList<>();7for (int i0 = 0; i < arr.length7; i++) {8    if (arr[i] == target) {⋯21 passes — pass 1 is the card abovepassi
10
21
32
43
54
65
76
80
91
⋯ 10 more passes ⋯
205
216
4if (arr[i] == target)pass 1 of 5⋯7for (int i = 0; i < arr.length; i++) {8    if (arr[i]3 == target3) {9        indices.add(i0);10    }⋯All 5 passes — pass 1 is the card abovepassarr[i]itarget
1303
2323
3343
4363
5939
5return indices;⋯11    }12    return indices[0, 2, 4, 6];13}⋯
6System.out.println("All 3's at: " + findAll(numbers, 3));⋯18System.out.println("Array: " + java.util.Arrays.toString(numbers));19System.out.println("All 3's at: " + findAll(numbers, 3));20System.out.println("All 9's at: " + findAll(numbers, 9));21System.out.println("All 5's at: " + findAll(numbers, 5));⋯outputAll 3's at: [0, 2, 4, 6]
7return indices;⋯11    }12    return indices[3];13}⋯
8System.out.println("All 9's at: " + findAll(numbers, 9));⋯19    System.out.println("All 3's at: " + findAll(numbers, 3));20    System.out.println("All 9's at: " + findAll(numbers, 9));21    System.out.println("All 5's at: " + findAll(numbers, 5));22}⋯outputAll 9's at: [3]
9return indices;⋯11    }12    return indices[];13}⋯
10System.out.println("All 5's at: " + findAll(numbers, 5));⋯20    System.out.println("All 9's at: " + findAll(numbers, 9));21    System.out.println("All 5's at: " + findAll(numbers, 5));22}⋯outputAll 5's at: []

All 3 passes — pass 1 is the card above
pass	`target`	`indices`
1	3	[]
2	9	[]
3	5	[]

21 passes — pass 1 is the card above
pass	`i`
1	0
2	1
3	2
4	3
5	4
6	5
7	6
8	0
9	1
⋯ 10 more passes ⋯
20	5
21	6

All 5 passes — pass 1 is the card above
pass	`arr[i]`	`i`	`target`
1	3	0	3
2	3	2	3
3	3	4	3
4	3	6	3
5	9	3	9

Predicate Search

                            Predicate.java
                        
Replay: real traced execution (multi-file project)

                            public class Predicate {
    interface IntPredicate {
        boolean test(int value);
    }

    static int findFirst(int[] arr, IntPredicate condition) {
        for (int i = 0; i < arr.length; i++) {
            if (condition.test(arr[i])) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] numbers = {3, 7, 12, 5, 18, 9};

        System.out.println("Array: " + java.util.Arrays.toString(numbers));
        int evenIdx = findFirst(numbers, x -> x % 2 == 0);
        System.out.println("First even at index: " + evenIdx);
        int largeIdx = findFirst(numbers, x -> x > 10);
        System.out.println("First > 10 at index: " + largeIdx);
        int negIdx = findFirst(numbers, x -> x < 0);
        System.out.println("First negative at index: " + negIdx);
    }
}

                        
1public static void main(String[] args)⋯15public static void main(String[] args) {16    int[] numbers = {3, 7, 12, 5, 18, 9};17    18    System.out.println("Array: " + java.util.Arrays.toString(numbers));19    int evenIdx = findFirst(numbers, x -> x % 2 == 0);20    System.out.println("First even at index: " + evenIdx);⋯outputArray: [3, 7, 12, 5, 18, 9]
2static int findFirst(int[] arr, IntPredicate condition)pass 1 of 3⋯6static int findFirst(int[] arr, IntPredicate condition⟨Predicate lambda A⟩) {7    for (int i = 0; i < arr.length; i++) {⋯All 3 passes — pass 1 is the card abovepassconditionarr[i]i
1⟨Predicate lambda A⟩122
2⟨Predicate lambda B⟩122
3⟨Predicate lambda C⟩——
3for (int i = 0; i < arr.length; i++)pass 1 of 12⋯6static int findFirst(int[] arr, IntPredicate condition) {7    for (int i0 = 0; i < arr.length6; i++) {8        if (condition.test(arr[i])) {⋯All 12 passes — pass 1 is the card abovepassiarr[i]
10—
21—
3212
40—
51—
6212
70—
81—
92—
103—
114—
125—
4if (condition.test(arr[i]))pass 1 of 2⋯7for (int i = 0; i < arr.length; i++) {8    if (condition.test(arr[i]12)) {9        return i2;10    }⋯
5evenIdx ← 2⋯18System.out.println("Array: " + java.util.Arrays.toString(numbers));19int evenIdx→ 2 = findFirst(numbers, x -> x % 2 == 0);20System.out.println("First even at index: " + evenIdx2);21int largeIdx = findFirst(numbers, x -> x > 10);22System.out.println("First > 10 at index: " + largeIdx);⋯outputFirst even at index: 2
6if (condition.test(arr[i]))pass 2 of 2⋯7for (int i = 0; i < arr.length; i++) {8    if (condition.test(arr[i]12)) {9        return i2;10    }⋯
7largeIdx ← 2⋯20System.out.println("First even at index: " + evenIdx);21int largeIdx→ 2 = findFirst(numbers, x -> x > 10);22System.out.println("First > 10 at index: " + largeIdx2);23int negIdx = findFirst(numbers, x -> x < 0);24System.out.println("First negative at index: " + negIdx);⋯outputFirst > 10 at index: 2
8return -1;⋯11    }12    return -1;13}⋯
9negIdx ← -1⋯22    System.out.println("First > 10 at index: " + largeIdx);23    int negIdx→ -1 = findFirst(numbers, x -> x < 0);24    System.out.println("First negative at index: " + negIdx-1);25}⋯outputFirst negative at index: -1

All 3 passes — pass 1 is the card above
pass	`condition`	`arr[i]`	`i`
1	⟨Predicate lambda A⟩	12	2
2	⟨Predicate lambda B⟩	12	2
3	⟨Predicate lambda C⟩	—	—

All 12 passes — pass 1 is the card above
pass	`i`	`arr[i]`
1	0	—
2	1	—
3	2	12
4	0	—
5	1	—
6	2	12
7	0	—
8	1	—
9	2	—
10	3	—
11	4	—
12	5	—

Predicate Search Instead of searching for one value, search for the first element that satisfies a condition.

Practical Use

Small inventories, recent items, and unsorted collections are natural places for linear search.

                            Practical.java
                        
Replay: real traced execution (multi-file project)

                            public class Practical {
    record Product(String id, String name, double price) {}

    static Product findById(Product[] inventory, String targetId) {
        for (Product p : inventory) {
            if (p.id().equals(targetId)) {
                return p;
            }
        }
        return null;  // not found
    }

    static Product findCheapest(Product[] inventory) {
        if (inventory.length == 0) return null;

        Product cheapest = inventory[0];
        for (int i = 1; i < inventory.length; i++) {
            if (inventory[i].price() < cheapest.price()) {
                cheapest = inventory[i];
            }
        }
        return cheapest;
    }

    public static void main(String[] args) {
        Product[] inventory = {
            new Product("A101", "Widget", 9.99),
            new Product("B202", "Gadget", 19.99),
            new Product("C303", "Doohickey", 4.99),
            new Product("D404", "Thingamajig", 14.99)
        };

        System.out.println("Inventory:");
        for (Product p : inventory) {
            System.out.println("  " + p);
        }

        System.out.println("\nSearch by ID:");
        Product found = findById(inventory, "C303");
        System.out.println("Found: " + found);

        Product notFound = findById(inventory, "X999");
        System.out.println("Not found: " + notFound);

        System.out.println("\nCheapest product:");
        System.out.println(findCheapest(inventory));
    }
}

                        
1public static void main(String[] args)⋯25public static void main(String[] args) {26    Product[] inventory = {27        new Product("A101", "Widget", 9.99),28        new Product("B202", "Gadget", 19.99),29        new Product("C303", "Doohickey", 4.99),30        new Product("D404", "Thingamajig", 14.99)31    };3233    System.out.println("Inventory:");34    for (Product p : inventory) {⋯outputInventory:
2for (Product p : inventory)pass 1 of 4⋯33System.out.println("Inventory:");34for (Product pProduct[id=A101, name=Widget, price=9.99] : inventory) {35    System.out.println("  " + pProduct[id=A101, name=Widget, price=9.99]);36}⋯output  Product[id=A101, name=Widget, price=9.99]All 4 passes — pass 1 is the card abovepassp
1Product[id=A101, name=Widget, price=9.99]
2Product[id=B202, name=Gadget, price=19.99]
3Product[id=C303, name=Doohickey, price=4.99]
4Product[id=D404, name=Thingamajig, price=14.99]
3Product found = findById(inventory, "C303");⋯38System.out.println("\nSearch by ID:");39Product found = findById(inventory, "C303");40System.out.println("Found: " + found);⋯output
Search by ID:
4static Product findById(Product[] inventory, String targetId)pass 1 of 2⋯4static Product findById(Product[] inventory, String targetIdC303) {5    for (Product p : inventory) {⋯
5for (Product p : inventory)pass 1 of 7⋯4static Product findById(Product[] inventory, String targetId) {5    for (Product pProduct[id=A101, name=Widget, price=9.99] : inventory) {6        if (p.id().equals(targetId)) {⋯All 7 passes — pass 1 is the card abovepassptargetId
1Product[id=A101, name=Widget, price=9.99]—
2Product[id=B202, name=Gadget, price=19.99]—
3Product[id=C303, name=Doohickey, price=4.99]C303
4Product[id=A101, name=Widget, price=9.99]—
5Product[id=B202, name=Gadget, price=19.99]—
6Product[id=C303, name=Doohickey, price=4.99]—
7Product[id=D404, name=Thingamajig, price=14.99]—
6if (p.id().equals(targetId))⋯5for (Product p : inventory) {6    if (p.id().equals(targetIdC303)) {7        return pProduct[id=C303, name=Doohickey, price=4.99];8    }⋯
7found ← Product[id=C303, name=Doohickey, price=4.99]⋯38System.out.println("\nSearch by ID:");39Product found→ Product[id=C303, name=Doohickey, price=4.99] = findById(inventory, "C303");40System.out.println("Found: " + foundProduct[id=C303, name=Doohickey, price=4.99]);4142Product notFound = findById(inventory, "X999");43System.out.println("Not found: " + notFound);⋯outputFound: Product[id=C303, name=Doohickey, price=4.99]
8static Product findById(Product[] inventory, String targetId)pass 2 of 2⋯4static Product findById(Product[] inventory, String targetIdX999) {5    for (Product p : inventory) {⋯
9return null;  // not found⋯9    }10    return null;  // not found11}⋯
10notFound ← null⋯42    Product notFound→ null = findById(inventory, "X999");43    System.out.println("Not found: " + notFoundnull);4445    System.out.println("\nCheapest product:");46    System.out.println(findCheapest(inventory));47}⋯outputNot found: null

Cheapest product:
11cheapest ← Product[id=A101, name=Widget, price=9.99]⋯13static Product findCheapest(Product[] inventory) {14    if (inventory.length == 0) return null;15    16    Product cheapest→ Product[id=A101, name=Widget, price=9.99] = inventory[0]Product[id=A101, name=Widget, price=9.99];17    for (int i = 1; i < inventory.length; i++) {⋯
12for (int i = 1; i < inventory.length; i++)pass 1 of 3⋯16Product cheapest = inventory[0];17for (int i1 = 1; i < inventory.length4; i++) {18    if (inventory[i].price() < cheapest.price()) {⋯All 3 passes — pass 1 is the card abovepassiinventory[i]cheapest
11——
22Product[id=C303, name=Doohickey, price=4.99]Product[id=C303, name=Doohickey, price=4.99]
33——
13cheapest ← Product[id=C303, name=Doohickey, price=4.99]⋯17for (int i = 1; i < inventory.length; i++) {18    if (inventory[i]Product[id=C303, name=Doohickey, price=4.99].price() < cheapest.price()) {19        cheapest→ Product[id=C303, name=Doohickey, price=4.99] = inventory[i]Product[id=C303, name=Doohickey, price=4.99];20    }⋯values this step2i
14return cheapest;⋯21    }22    return cheapestProduct[id=C303, name=Doohickey, price=4.99];23}⋯
15System.out.println(findCheapest(inventory));⋯45    System.out.println("\nCheapest product:");46    System.out.println(findCheapest(inventory));47}⋯outputProduct[id=C303, name=Doohickey, price=4.99]

All 4 passes — pass 1 is the card above
pass	`p`
1	Product[id=A101, name=Widget, price=9.99]
2	Product[id=B202, name=Gadget, price=19.99]
3	Product[id=C303, name=Doohickey, price=4.99]
4	Product[id=D404, name=Thingamajig, price=14.99]

All 7 passes — pass 1 is the card above
pass	`p`	`targetId`
1	Product[id=A101, name=Widget, price=9.99]	—
2	Product[id=B202, name=Gadget, price=19.99]	—
3	Product[id=C303, name=Doohickey, price=4.99]	C303
4	Product[id=A101, name=Widget, price=9.99]	—
5	Product[id=B202, name=Gadget, price=19.99]	—
6	Product[id=C303, name=Doohickey, price=4.99]	—
7	Product[id=D404, name=Thingamajig, price=14.99]	—

All 3 passes — pass 1 is the card above
pass	`i`	`inventory[i]`	`cheapest`
1	1	—	—
2	2	Product[id=C303, name=Doohickey, price=4.99]	Product[id=C303, name=Doohickey, price=4.99]
3	3	—	—

Exercise: Practical.java

Implement a linear search that returns the last occurrence of a target value

pass	`i`	`arr[i]`
1	0	—
2	1	—
3	2	12
4	0	—
5	1	—
6	2	12
7	0	—
8	1	—
9	2	—
10	3	—
11	4	—
12	5	—

pass	`i`	`arr[i]`
1	0	—
2	1	—
3	2	12
4	0	—
5	1	—
6	2	12
7	0	—
8	1	—
9	2	—
10	3	—
11	4	—
12	5	—

pass	`i`	`arr[i]`
1	0	—
2	1	—
3	2	12
4	0	—
5	1	—
6	2	12
7	0	—
8	1	—
9	2	—
10	3	—
11	4	—
12	5	—