Implement Binary Search and Linear Search - Java

Category: Medium | Concepts used: Searching algorithms, divide and conquer

---

Problem Statement

Given an array and a target value, find the index of the target (or report it’s not found).

• Linear search: works on any array (sorted or not).
• Binary search: requires a sorted array, but is much faster.

Input : [3, 7, 1, 9], target=9 (unsorted, linear search)      Output: index 3
Input : [1, 3, 5, 7, 9], target=7 (sorted, binary search)       Output: index 3

Examples (with edge scenarios)

#	Input	Target	Output	Why
1	[1,3,5,7,9]	7	index 3	Found in the middle-right region
2	[1,3,5,7,9]	10	-1 (not found)	Target doesn’t exist in array
3	[]	any	-1	Empty array — nothing to search
4	[5] (single element)	5	index 0	Trivial match
5	[1,3,5,7,9]	1 (first element)	index 0	Edge of the search range

Common Fresher Mistake

Mistake	What happens	Fix
Using binary search on an unsorted array	Produces wrong/inconsistent results — binary search assumes sorted order to eliminate halves correctly	Always confirm the array is sorted before using binary search; otherwise use linear search
Off-by-one errors in binary search’s low/high/mid bounds	Infinite loop, missed elements, or ArrayIndexOutOfBoundsException	Carefully use mid = low + (high - low) / 2 (avoids overflow too) and update bounds correctly based on comparison

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether the array may be null or empty, whether duplicates and original order matter, whether the method may modify the input, and whether the answer should contain values or original indices. These choices can change both the code and the best data structure.

Analogy: Guessing a Secret Number

Imagine you are playing a guessing game where you need to find a secret number between 1 and 100:

• Linear Search (The Guessing Loop): You guess 1, then 2, then 3, checking every single number in order. If the secret number is 99, it takes you 99 guesses. This is slow and repetitive.
• Binary Search (The Halfway Split):
  • Since the numbers are sorted, you guess the exact middle: 50.
  • The host says: “Too low!”
  • Knowing that all numbers below 50 are now useless, you cross off the entire range 1 to 50. Your new search space is 51 to 100.
  • You guess the middle of this new range: 75.
  • The host says: “Too high!”
  • You cross off 75 to 100. Your new search space is 51 to 74.
  • By repeatedly halving the search space, you find the exact number in at most 7 steps instead of 100!

---

Solution 1 — Linear Search (Works on Any Array)

Intuition

Without any assumption about order, the only reliable way to find a target is to check every element one at a time, starting from the beginning, until we find a match (or run out of elements).

public class LinearSearch {
    public 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
    }

public static void main(String[] args) {
        int[] arr = {3, 7, 1, 9};
        System.out.println(linearSearch(arr, 9));  // 3
        System.out.println(linearSearch(arr, 100)); // -1
    }
}

Output:

3
-1

Dry Run (arr = [3, 7, 1, 9], target = 9)

i=0: arr[0]=3, not 9
i=1: arr[1]=7, not 9
i=2: arr[2]=1, not 9
i=3: arr[3]=9, MATCH! -> return 3

Interviewer’s take

Correct and works for any array (sorted or not) — a fine, simple baseline. Interviewers will typically follow up asking about a faster approach if the array is sorted, leading into binary search.

Follow-up questions you might get:

• “What’s the time complexity?” → O(n) — worst case, checks every element.
• “If the array were sorted, could you do better?” → leads to Solution 2.

---

Solution 2 — Binary Search (Iterative, Requires Sorted Array)

Intuition

If the array is sorted, we can eliminate half the remaining search space with every single comparison. Check the middle element: if it’s the target, done. If the target is smaller, it must be somewhere in the left half (since everything to the right of the middle is even bigger) — so we discard the right half entirely. If the target is bigger, discard the left half. Repeat on the remaining half until found or nothing’s left.

public class BinarySearchIterative {
    public static int binarySearch(int[] sortedArr, int target) {
        int low = 0, high = sortedArr.length - 1;

while (low <= high) {
            int mid = low + (high - low) / 2; // avoids potential overflow vs (low+high)/2

if (sortedArr[mid] == target) {
                return mid; // found!
            } else if (sortedArr[mid] < target) {
                low = mid + 1; // target must be in the right half
            } else {
                high = mid - 1; // target must be in the left half
            }
        }
        return -1; // not found
    }

public static void main(String[] args) {
        int[] sorted = {1, 3, 5, 7, 9};
        System.out.println(binarySearch(sorted, 7));  // 3
        System.out.println(binarySearch(sorted, 10)); // -1
    }
}

Output:

3
-1

Dry Run (sortedArr = [1,3,5,7,9], target = 7)

low=0, high=4

Step 1: mid=0+(4-0)/2=2, sortedArr[2]=5
  5 < 7 -> target is in right half -> low=3

Step 2: mid=3+(4-3)/2=3, sortedArr[3]=7
  7 == 7 -> MATCH! return 3

Interviewer’s take

This is the preferred answer for sorted arrays — O(log n) time, dramatically faster than linear search for large arrays (e.g., for 1 million elements, binary search needs at most ~20 comparisons vs. up to 1 million for linear search). The mid = low + (high - low) / 2 formula (instead of (low+high)/2) is a subtle but important detail — it avoids potential integer overflow for very large arrays with large index values.

Follow-up questions you might get:

• “Why is low + (high-low)/2 better than (low+high)/2?” → low + high could theoretically overflow int if both are very large (close to Integer.MAX_VALUE), even though the actual midpoint value wouldn’t; the alternative formula avoids that overflow risk entirely.
• “Can you implement this recursively?” → leads to Solution 3.
• “What if the array isn’t sorted?” → Binary search simply won’t work correctly — must sort first (which costs O(n log n)) or use linear search instead if sorting isn’t an option.

---

Solution 3 — Binary Search (Recursive Version)

Intuition

The same “eliminate half each time” idea, but expressed recursively: each recursive call handles a smaller sub-range (low to high), narrowing down exactly like the iterative loop did, just via function calls instead of a while loop.

public class BinarySearchRecursive {
    public static int binarySearch(int[] sortedArr, int target, int low, int high) {
        if (low > high) {
            return -1; // search space exhausted, not found
        }

int mid = low + (high - low) / 2;

if (sortedArr[mid] == target) {
            return mid;
        } else if (sortedArr[mid] < target) {
            return binarySearch(sortedArr, target, mid + 1, high); // search right half
        } else {
            return binarySearch(sortedArr, target, low, mid - 1);   // search left half
        }
    }

public static void main(String[] args) {
        int[] sorted = {1, 3, 5, 7, 9};
        System.out.println(binarySearch(sorted, 7, 0, sorted.length - 1)); // 3
    }
}

Output:

3

Interviewer’s take

Equally valid — same O(log n) time complexity. The trade-off: recursion uses O(log n) call stack space, while the iterative version uses O(1) space. Mentioning this trade-off proactively is a nice touch.

---

📊 Visual Flowchart

graph TD
    Start["Input: Sorted Array, Target T"] --> Init["low = 0, high = length - 1"]
    Init --> Loop{"low <= high?"}
    Loop -->|Yes| CalcMid["mid = low + (high - low) / 2"]
    CalcMid --> CheckMatch{"arr[mid] == T?"}
    CheckMatch -->|Yes| RetIndex["Return mid"]
    CheckMatch -->|No| CheckSide{"arr[mid] < T?"}
    CheckSide -->|Yes| MoveRight["low = mid + 1"]
    CheckSide -->|No| MoveLeft["high = mid - 1"]
    MoveRight --> Loop
    MoveLeft --> Loop
    Loop -->|No| RetNotFound["Return -1 (Not Found)"]

---

Final Verdict — Which Solution Should You Give?

Array not sorted?  ──►  Solution 1 (Linear Search) — only option, O(n)
Array sorted?      ──►  Solution 2 or 3 (Binary Search) — O(log n), much faster

• Always clarify whether the input is sorted before choosing your approach — this single question often matters more than the code itself.
• Binary search (iterative or recursive) is the expected “impressive” answer whenever sorted input is confirmed.

---

Quick Recap

Approach	Time	Space	Requires sorted input?
Linear Search	O(n)	O(1)	No
Binary Search (iterative)	O(log n)	O(1)	Yes
Binary Search (recursive)	O(log n)	O(log n) call stack	Yes