Check if a given number exists in an array

• Linear search – walk the array comparing each element with the target.
• Early exit – return true the moment a match is found, avoiding unnecessary work.
• Worst case O(n) – when the target is absent or at the very end, every element is checked.
• O(1) space – no extra data structures are needed.
• Unsorted data – works on any array regardless of order, unlike binary search which requires sorting.

What is the problem?

Given an array and a target value, determine whether the target exists anywhere in the array. In a banking context, Priya disputed a charge and the system needs to verify whether a specific cheque amount Rs.9800 was ever cleared on her current account CUR3001 at National Bank of India.

How does the algorithm work?

Loop over each element and compare it with the target. Return true the moment a match is found. If the loop ends without finding a match, return false.

package com.bank.service;

import java.math.BigDecimal;

public class ChequeVerifier {

    public static boolean chequeExists(BigDecimal[] clearedAmounts, BigDecimal target) {
        if (clearedAmounts == null) {
            throw new IllegalArgumentException("Cleared amounts cannot be null");
        }
        for (BigDecimal amount : clearedAmounts) {
            if (target.compareTo(amount) == 0) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        BigDecimal[] cleared = {
            new BigDecimal("15000.00"),
            new BigDecimal("9800.00"),
            new BigDecimal("4500.00"),
            new BigDecimal("22000.00")
        };
        BigDecimal target = new BigDecimal("9800");
        boolean found = chequeExists(cleared, target);
        System.out.println("Cheque Rs.9800 cleared: " + found);
    }
}

Cheque Rs.9800 cleared: true

Why is the early return important?

The early return stops the scan the moment the answer is known. If the target is the first element, the method returns in O(1). Without the early return, you would scan the entire array every time, wasting work when the match appears early.

What is the time and space complexity?

• Best case: O(1) when the target is the first element.
• Worst case: O(n) when the target is absent or at the very end.
• Average case: O(n/2) which simplifies to O(n).
• Space: O(1) because no extra data structures are allocated.

How is this different from counting occurrences?

An existence check only needs the first match and can stop immediately, while counting must scan every element. Use linear search when the question is "does it exist?" and counting when the question is "how many times?"

| Aspect | Existence Check | Count Occurrences |
|---|---|---|
| Early exit | Yes, at first match | No, must scan all |
| Returns | boolean | int |
| Best case | O(1) | O(n) |
| Worst case | O(n) | O(n) |

When should you use binary search instead?

If the array is sorted, binary search finds the target in O(log n) by repeatedly halving the search range. But sorting first costs O(n log n), so it only pays off if you search the same array many times. For a single lookup on unsorted data, linear search is optimal.

// Binary search on sorted array
import java.util.Arrays;

Arrays.sort(cleared); // O(n log n)
int index = Arrays.binarySearch(cleared, target); // O(log n)
boolean found = (index >= 0);

What are common mistakes?

The most common mistake is forgetting the return false after the loop, which causes a compile error. Another mistake is using == for BigDecimal comparison, which checks references, not values.

// Wrong: reference comparison
if (amount == target) { return true; } // compares memory addresses

// Wrong: equals with scale sensitivity
if (amount.equals(target)) { return true; } // misses 9800 vs 9800.00

// Correct: value comparison
if (target.compareTo(amount) == 0) { return true; }

What about using Java collections?

Java's List.contains() performs linear search internally with equals. For BigDecimal, this has the scale problem. A HashSet gives O(1) average lookup but also uses equals and hashCode, so you must normalise with stripTrailingZeros() before adding to the set.

import java.util.HashSet;
import java.util.Set;

Set<BigDecimal> clearedSet = new HashSet<>();
for (BigDecimal amount : cleared) {
    clearedSet.add(amount.stripTrailingZeros());
}
boolean found = clearedSet.contains(target.stripTrailingZeros());

What should a senior engineer know?

A senior engineer knows that for repeated lookups on the same data, building a HashSet once (O(n)) and then looking up each query in O(1) is far better than scanning the array each time. In a dispute resolution system that checks thousands of cheques against a cleared list, the set-based approach turns an O(n*m) problem into O(n+m). The senior also mentions that for very large sorted datasets, binary search or a TreeSet gives O(log n) per query with no hashing overhead.