Java and Object-Oriented Programming FoundationLesson 63 / 115

Algorithms and Problem Solving with Java

Linear Search and Binary Search

ReadingPreview

You are viewing a free preview lesson.

Lesson Overview

Searching programming-এর সবচেয়ে common operations-এর একটি।

Examples:

এই learner কি list-এ আছে?
এই course code কি পাওয়া গেছে?
এই score কি array-তে আছে?
এই ID কোন position-এ আছে?

Search করার অনেক strategy আছে।

এই lesson-এ আমরা দুইটি fundamental search algorithm শিখব:

Linear Search
Binary Search

Linear Search একে একে values check করে।

Binary Search sorted data ব্যবহার করে প্রতি step-এ search space-এর বড় একটি অংশ বাদ দেয়।

এই lesson-এ আমরা শিখব:

  • What a search algorithm is
  • Linear Search
  • Returning boolean vs index
  • Best and worst case
  • O(n) search
  • Binary Search
  • Why sorted input is required
  • left, right, and middle
  • Implementing Binary Search
  • Tracing Binary Search
  • O(log n)
  • Handling missing values
  • Duplicate values
  • Arrays.binarySearch()
  • Collections.binarySearch()
  • Linear Search vs Binary Search
  • When sorting before searching makes sense
  • Common search mistakes

What Is Searching?

Searching means trying to determine whether a target value exists in a collection of data।

Example:

int[] numbers = {
        10,
        20,
        30,
        40
};

Question:

Does 30 exist?

or:

At which index does 30 exist?

These are search problems।

Search Result Design

A search method can return different kinds of results depending on what the caller needs।

Boolean Search

If we only care whether the value exists:

static boolean contains(
        int[] numbers,
        int target
)

Result:

true
false

Index Search

If we care about position:

static int indexOf(
        int[] numbers,
        int target
)

Result:

0 or greater → found index
-1           → not found

Returning the Value Itself

For objects, a search might eventually return:

Course
Learner
Enrollment

or perhaps:

Optional<Course>

We'll study Optional later।

For now, arrays make boolean and index-based search easy to understand।

Linear Search

Linear Search checks values one by one।

Example:

[10, 20, 30, 40, 50]

Target = 40

Search process:

10 → no
20 → no
30 → no
40 → yes

Then stop।

Linear Search Implementation

static boolean contains(
        int[] numbers,
        int target
) {
    for (
            int number
            : numbers
    ) {
        if (
                number == target
        ) {
            return true;
        }
    }

    return false;
}

Why Return Immediately?

Once the target is found:

return true;

There is no reason to inspect remaining values।

This is an early-return optimization and also makes the method easier to read।

Linear Search by Index

If we need the position:

static int indexOf(
        int[] numbers,
        int target
) {
    for (
            int i = 0;
            i < numbers.length;
            i++
    ) {
        if (
                numbers[i] == target
        ) {
            return i;
        }
    }

    return -1;
}

Why -1?

Valid indexes start from:

0

So:

-1

can safely represent:

Not found

Example

int[] numbers = {
        10,
        20,
        30,
        40
};

int index =
        indexOf(
                numbers,
                30
        );

System.out.println(
        index
);

Output:

2

Linear Search Works on Unsorted Data

This is important।

Example:

int[] numbers = {
        90,
        10,
        70,
        30,
        20
};

Linear Search works perfectly fine।

It does not require:

Sorted input

because it simply checks each value।

Linear Search Best Case

Suppose:

int[] numbers = {
        42,
        10,
        20,
        30
};

Target:

42

The first comparison succeeds।

Best case:

O(1)

Linear Search Worst Case

Suppose target is:

30

at the final position।

Or target does not exist at all।

Then every element may need to be checked।

Worst case:

O(n)

Linear Search Space Complexity

The iterative implementation uses only a few local variables।

Additional space:

O(1)

Searching Strings

Example:

static int indexOf(
        String[] values,
        String target
) {
    for (
            int i = 0;
            i < values.length;
            i++
    ) {
        if (
                values[i].equals(
                        target
                )
        ) {
            return i;
        }
    }

    return -1;
}

Be Careful with null

If array values may contain null, this can fail:

values[i].equals(
        target
);

because:

values[i]

might be null।

A safer comparison can use:

Objects.equals(
        values[i],
        target
);

with:

import java.util.Objects;

Example:

static int indexOf(
        String[] values,
        String target
) {
    for (
            int i = 0;
            i < values.length;
            i++
    ) {
        if (
                Objects.equals(
                        values[i],
                        target
                )
        ) {
            return i;
        }
    }

    return -1;
}

Linear Search with Objects

Suppose:

record Course(
        String code,
        String title
) {
}

Search by code:

static int indexOfCourse(
        Course[] courses,
        String code
) {
    for (
            int i = 0;
            i < courses.length;
            i++
    ) {
        if (
                courses[i]
                        .code()
                        .equals(
                                code
                        )
        ) {
            return i;
        }
    }

    return -1;
}

The search criterion does not have to be the entire object।

You can search based on a specific field।

Searching Collections

With a List, Java already provides:

contains(...)
indexOf(...)

Example:

List<String> courses =
        List.of(
                "Java",
                "Backend",
                "System Design"
        );

boolean found =
        courses.contains(
                "Backend"
        );

For an ArrayList, this is generally a linear scan:

O(n)

Binary Search

Binary Search is much faster for repeated searching on sorted data।

Core requirement:

The data must be sorted.

Example:

[10, 20, 30, 40, 50, 60, 70]

Target:

60

Instead of checking from the beginning, Binary Search looks near the middle first।

Binary Search Intuition

Start:

[10, 20, 30, 40, 50, 60, 70]

Middle:

40

Target:

60

Since:

60 > 40

everything to the left of 40 can be ignored।

Remaining:

[50, 60, 70]

Middle:

60

Found।

Why Can We Ignore Half?

Because the data is sorted।

If:

target > middle value

then every value to the left is also too small।

If:

target < middle value

then every value to the right is too large।

That is what makes Binary Search possible।

Binary Search Cannot Reliably Work on Unsorted Data

Suppose:

[80, 10, 60, 20, 90]

Target:

90

If the middle is:

60

and we conclude:

90 > 60

there is no guarantee values on the left are smaller।

The ordering assumption is broken।

Therefore Binary Search requires sorted input।

Binary Search State

We maintain three important positions:

left
right
middle

Example:

int left =
        0;

int right =
        numbers.length - 1;

Then:

int middle =
        left
        + (
                right - left
        ) / 2;

Why This Middle Formula?

You may also see:

(left + right) / 2

For normal small arrays this often works।

But:

left + right

can theoretically overflow int for very large index values।

This version:

left
+ (
        right - left
) / 2

avoids that problem।

It is a good habit।

Full Binary Search Implementation

static int binarySearch(
        int[] sortedNumbers,
        int target
) {
    int left =
            0;

    int right =
            sortedNumbers.length - 1;

    while (
            left <= right
    ) {
        int middle =
                left
                + (
                        right - left
                ) / 2;

        int value =
                sortedNumbers[middle];

        if (
                value == target
        ) {
            return middle;
        }

        if (
                value < target
        ) {
            left =
                    middle + 1;
        } else {
            right =
                    middle - 1;
        }
    }

    return -1;
}

Why left <= right?

The search is valid while there is at least one candidate position remaining।

If:

left == right

there is exactly one candidate left।

So it still needs to be checked।

When:

left > right

the search range is empty।

Trace Binary Search

Array:

[10, 20, 30, 40, 50, 60, 70]

Target:

60

Initial:

left  = 0
right = 6

Middle:

3

Value:

40

Since:

60 > 40

set:

left = 4

Second Step

Search range:

index 4 to 6

Values:

50 60 70

Now:

left  = 4
right = 6
middle = 5

Value:

60

Target found।

Return:

5

Trace Missing Value

Array:

[10, 20, 30, 40, 50]

Target:

35

Start:

left  = 0
right = 4
middle = 2
value = 30

Since:

35 > 30

new:

left = 3

Next Step

left  = 3
right = 4
middle = 3
value = 40

Since:

35 < 40

new:

right = 2

Now:

left = 3
right = 2

So:

left > right

Search ends।

Return:

-1

Binary Search Complexity

Each step removes approximately half the remaining candidates।

Example:

1,024 elements
↓
512
↓
256
↓
128
↓
64
↓
32
↓
16
↓
8
↓
4
↓
2
↓
1

Only around:

10 steps

Worst-case time complexity:

O(log n)

Binary Search Space Complexity

Our iterative implementation uses:

left
right
middle
value

No memory grows with input size।

Extra space:

O(1)

Recursive Binary Search

Binary Search can also be implemented recursively।

Example:

static int binarySearch(
        int[] sortedNumbers,
        int target
) {
    return binarySearch(
            sortedNumbers,
            target,
            0,
            sortedNumbers.length - 1
    );
}

static int binarySearch(
        int[] sortedNumbers,
        int target,
        int left,
        int right
) {
    if (
            left > right
    ) {
        return -1;
    }

    int middle =
            left
            + (
                    right - left
            ) / 2;

    int value =
            sortedNumbers[middle];

    if (
            value == target
    ) {
        return middle;
    }

    if (
            value < target
    ) {
        return binarySearch(
                sortedNumbers,
                target,
                middle + 1,
                right
        );
    }

    return binarySearch(
            sortedNumbers,
            target,
            left,
            middle - 1
    );
}

Iterative vs Recursive Binary Search

Both have time:

O(log n)

But iterative version uses:

O(1)

extra space।

Recursive version uses call-stack space:

O(log n)

For Java production code, iterative Binary Search is often preferable unless recursion makes a specific implementation clearer।

Binary Search Best Case

If target is exactly at the first middle position:

O(1)

Example:

[10, 20, 30, 40, 50]

Target = 30

First comparison finds it।

Worst case remains:

O(log n)

Linear Search vs Binary Search

Linear Search

Requirements:

No sorting required

Worst time:

O(n)

Works naturally with unsorted data।

Binary Search

Requirements:

Sorted data

Worst time:

O(log n)

Much faster on large sorted datasets।

Comparison Example

Suppose:

1,000,000 values

Linear Search worst case:

around 1,000,000 comparisons

Binary Search:

around 20 comparisons

That is a huge difference।

But Sorting Also Has a Cost

Suppose your array is unsorted:

[50, 10, 90, 20, 70]

You could:

Sort
Then binary search

But sorting itself has a cost।

Efficient sorting is commonly around:

O(n log n)

Then one Binary Search:

O(log n)

Total:

O(n log n)

for the sort + one search।

One Search on Unsorted Data

If you need only one lookup:

Linear Search → O(n)

may be better than:

Sort + Binary Search
→ O(n log n)

because you avoid sorting entirely।

Many Searches

Suppose the data is stable and you perform:

10,000 searches

Then sorting once may be worthwhile।

Conceptually:

Sort once
+
many O(log n) searches

can outperform:

many O(n) linear searches

Search Strategy Depends on Context

Ask:

Is data already sorted?

How many searches will happen?

Does original order matter?

Will data change frequently?

Do I need exact index positions?

Could a HashMap or HashSet be better?

Binary Search is not automatically the best search strategy।

Hash-Based Lookup

If you only need membership checking:

Set<String> codes =
        new HashSet<>();

then:

codes.contains(
        target
);

is typically average:

O(1)

This can be even more suitable than Binary Search when:

Ordering is not required
Fast membership lookup matters
Additional memory is acceptable

Search by Key

Suppose you have:

CourseCode → Course

A Map<CourseCode, Course> may be more appropriate than repeatedly searching an array or list।

Example:

Map<String, String> courses =
        new HashMap<>();

courses.put(
        "JAVA",
        "Java Foundation"
);

Lookup:

courses.get(
        "JAVA"
);

Typical expected lookup:

O(1)

Again:

Choose the data structure based on access pattern.

Arrays.binarySearch()

Java provides Binary Search in:

java.util.Arrays

Example:

import java.util.Arrays;

public class Main {

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

        int index =
                Arrays.binarySearch(
                        numbers,
                        30
                );

        System.out.println(
                index
        );
    }
}

Output:

2

Found Result

When found:

result >= 0

and represents an index where the matching value was found।

Missing Result

When missing:

result < 0

The exact negative result encodes an insertion point।

For basic usage:

boolean found =
        Arrays.binarySearch(
                numbers,
                target
        ) >= 0;

is enough।

Understanding the Insertion Point

Suppose:

int[] numbers = {
        10,
        20,
        40,
        50
};

Search:

30

If inserted while preserving order, 30 belongs at index:

2

Arrays.binarySearch() returns a negative value encoding that insertion point using:

-(insertionPoint) - 1

So for insertion point 2:

-3

Recovering the Insertion Point

If:

int result =
        Arrays.binarySearch(
                numbers,
                target
        );

and:

result < 0

then:

int insertionPoint =
        -result - 1;

Example

int[] numbers = {
        10,
        20,
        40,
        50
};

int result =
        Arrays.binarySearch(
                numbers,
                30
        );

System.out.println(
        result
);

int insertionPoint =
        -result - 1;

System.out.println(
        insertionPoint
);

Output conceptually:

-3
2

Do You Need to Memorize This?

Not necessarily for everyday usage।

But it is useful to understand why a missing result is not always:

-1

Arrays.binarySearch() Still Requires Sorted Input

This is critical।

Incorrect:

int[] numbers = {
        50,
        10,
        30
};

Arrays.binarySearch(
        numbers,
        30
);

Do not expect meaningful behavior from unsorted input।

Correct:

Arrays.sort(
        numbers
);

int index =
        Arrays.binarySearch(
                numbers,
                30
        );

Collections.binarySearch()

For sorted List data, Java provides:

Collections.binarySearch(...)

Example:

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

public class Main {

    public static void main(String[] args) {
        List<Integer> numbers =
                new ArrayList<>(
                        List.of(
                                10,
                                20,
                                30,
                                40,
                                50
                        )
                );

        int index =
                Collections.binarySearch(
                        numbers,
                        30
                );

        System.out.println(
                index
        );
    }
}

Output:

2

Collections.binarySearch() Requirement

The list must be sorted according to the same ordering used by the search।

For natural ordering:

Collections.sort(
        numbers
);

then:

Collections.binarySearch(
        numbers,
        target
);

Binary Search and Custom Ordering

Later, when we learn Comparator, we may sort objects using custom ordering।

If a list is sorted using a comparator, Binary Search must use a compatible comparator।

Example conceptually:

Collections.binarySearch(
        courses,
        target,
        comparator
);

Sorting and searching must agree on the same ordering rule।

Duplicate Values

Suppose:

[10, 20, 20, 20, 30]

Search target:

20

Binary Search may return an index containing 20, but it is not necessarily guaranteed to be the first or last occurrence unless the API/algorithm is specifically designed for that।

Example

Possible result:

1
2
or
3

depending on implementation and search path।

If you need:

First occurrence

or:

Last occurrence

you need a modified Binary Search।

Find First Occurrence

Conceptually, when a match is found:

Record the index
Continue searching left

Example:

static int firstIndexOf(
        int[] sortedNumbers,
        int target
) {
    int left =
            0;

    int right =
            sortedNumbers.length - 1;

    int result =
            -1;

    while (
            left <= right
    ) {
        int middle =
                left
                + (
                        right - left
                ) / 2;

        if (
                sortedNumbers[middle]
                == target
        ) {
            result =
                    middle;

            right =
                    middle - 1;
        } else if (
                sortedNumbers[middle]
                < target
        ) {
            left =
                    middle + 1;
        } else {
            right =
                    middle - 1;
        }
    }

    return result;
}

Find Last Occurrence

When a match is found:

Record the index
Continue searching right

Example:

static int lastIndexOf(
        int[] sortedNumbers,
        int target
) {
    int left =
            0;

    int right =
            sortedNumbers.length - 1;

    int result =
            -1;

    while (
            left <= right
    ) {
        int middle =
                left
                + (
                        right - left
                ) / 2;

        if (
                sortedNumbers[middle]
                == target
        ) {
            result =
                    middle;

            left =
                    middle + 1;
        } else if (
                sortedNumbers[middle]
                < target
        ) {
            left =
                    middle + 1;
        } else {
            right =
                    middle - 1;
        }
    }

    return result;
}

These are good examples of adapting an algorithm to specific requirements।

Binary Search Is More Than Exact Lookup

The same idea can solve problems such as:

Find first value >= target
Find last value <= target
Find insertion position
Find boundary between false and true conditions

These are sometimes called:

Binary search on boundaries

We won't go deeply into advanced variations here, but it is useful to know Binary Search is broader than exact-value lookup।

Search and Sorted Strings

Example:

String[] names = {
        "Jalisa",
        "Nur",
        "Sakib",
        "Subu",
        "Sumu"
};

Because the array is sorted according to String natural ordering:

int index =
        Arrays.binarySearch(
                names,
                "Subu"
        );

can be used।

Sorting First

If input is:

String[] names = {
        "Sumu",
        "Sakib",
        "Nur",
        "Subu",
        "Jalisa"
};

then:

Arrays.sort(
        names
);

before:

Arrays.binarySearch(
        names,
        "Subu"
);

Sorting Mutates the Array

Remember:

Arrays.sort(
        names
);

changes the original order।

If original order matters:

String[] sorted =
        Arrays.copyOf(
                names,
                names.length
        );

Arrays.sort(
        sorted
);

Then search:

Arrays.binarySearch(
        sorted,
        target
);

Index Meaning After Sorting

This is subtle।

Suppose original:

Index 0 → Sumu
Index 1 → Sakib
Index 2 → Nur

After sorting:

Index 0 → Nur
Index 1 → Sakib
Index 2 → Sumu

Binary Search returns the index in the sorted array, not the original array।

If original position matters, sorting a copy and searching it does not directly answer:

Where was this item originally?

Search Requirements Matter

Always define the question precisely।

Do you need:

Existence?
Current sorted position?
Original position?
First occurrence?
Last occurrence?
Associated object?
Fast repeated lookup?

Different requirements can lead to different data structures and algorithms।

Common Mistake 1 — Binary Search on Unsorted Data

Wrong:

binarySearch(
        unsorted,
        target
);

Binary Search fundamentally depends on ordering।

Common Mistake 2 — Moving the Wrong Boundary

Suppose:

middle value < target

Then the target, if present, must be to the right।

Correct:

left =
        middle + 1;

Not:

right =
        middle - 1;

Common Mistake 3 — Forgetting +1 or -1

Bad:

left =
        middle;

or:

right =
        middle;

can cause the same middle index to be reconsidered repeatedly and may create an infinite loop।

Correct movement removes the already-checked position:

left =
        middle + 1;

or:

right =
        middle - 1;

Common Mistake 4 — Using < Instead of <=

This:

while (
        left < right
)

can skip the final single candidate in a standard exact Binary Search implementation if the rest of the logic is not adjusted accordingly।

The straightforward implementation uses:

while (
        left <= right
)

Common Mistake 5 — Sorting for One Search

If data is unsorted and you need one target lookup, sorting everything just to perform Binary Search may be more expensive than a simple linear scan।

Common Mistake 6 — Forgetting Sort Mutation

Arrays.sort(
        values
);

changes ordering।

If the original sequence carries meaning, preserve it।

Common Mistake 7 — Assuming Missing binarySearch() Result Is -1

Use:

result < 0

to detect absence।

The exact negative value may encode insertion position।

Common Mistake 8 — Assuming Duplicate Search Returns First Match

A normal Binary Search only promises a matching position, not necessarily the earliest duplicate।

Common Mistake 9 — Using Binary Search When Hash Lookup Fits Better

If your only requirement is frequent membership lookup and order is irrelevant:

HashSet

may be a better design।

Common Mistake 10 — Optimizing Without Considering Data Changes

Suppose you maintain a sorted array for Binary Search, but new values are constantly inserted।

Keeping an array sorted can itself be expensive।

Search cost is only one part of the data structure's lifecycle।

Practical Example — Course Code Search

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        String[] courseCodes = {
                "ALGORITHMS",
                "BACKEND",
                "JAVA",
                "SYSTEM-DESIGN"
        };

        String target =
                "JAVA";

        int index =
                Arrays.binarySearch(
                        courseCodes,
                        target
                );

        if (
                index >= 0
        ) {
            System.out.println(
                    target
                    + " found at index "
                    + index
            );
        } else {
            System.out.println(
                    target
                    + " not found"
            );
        }
    }
}

Practical Example — Linear Search Over Learners

record Learner(
        long id,
        String name
) {
}

Search:

static Learner findById(
        Learner[] learners,
        long id
) {
    for (
            Learner learner
            : learners
    ) {
        if (
                learner.id()
                == id
        ) {
            return learner;
        }
    }

    return null;
}

This is:

O(n)

For a very small in-memory array this may be perfectly reasonable।

For a large frequently queried dataset, a map keyed by ID may be a better structure।

Practical Example — Choose the Search Strategy

Scenario 1

You have:

20 values

Unsorted.

One search.

Good default:

Linear Search

Scenario 2

You have:

5 million sorted values

Many repeated searches.

Good candidate:

Binary Search

Scenario 3

You have:

Millions of IDs

Frequent membership checks.

Order irrelevant.

Good candidate:

HashSet

Scenario 4

You need:

ID → object lookup

Good candidate:

HashMap

Practice 1 — Linear Search

Implement:

static boolean contains(
        int[] numbers,
        int target
)

Solution

static boolean contains(
        int[] numbers,
        int target
) {
    for (
            int number
            : numbers
    ) {
        if (
                number == target
        ) {
            return true;
        }
    }

    return false;
}

Practice 2 — Index Search

Implement:

static int indexOf(
        String[] values,
        String target
)

Return -1 when missing।

Solution

static int indexOf(
        String[] values,
        String target
) {
    for (
            int i = 0;
            i < values.length;
            i++
    ) {
        if (
                values[i].equals(
                        target
                )
        ) {
            return i;
        }
    }

    return -1;
}

Practice 3 — Binary Search

Implement:

static int binarySearch(
        int[] sorted,
        int target
)

Solution

static int binarySearch(
        int[] sorted,
        int target
) {
    int left =
            0;

    int right =
            sorted.length - 1;

    while (
            left <= right
    ) {
        int middle =
                left
                + (
                        right - left
                ) / 2;

        if (
                sorted[middle]
                == target
        ) {
            return middle;
        }

        if (
                sorted[middle]
                < target
        ) {
            left =
                    middle + 1;
        } else {
            right =
                    middle - 1;
        }
    }

    return -1;
}

Practice 4 — Trace Binary Search

Array:

[10, 20, 30, 40, 50, 60, 70]

Target:

20

First middle:

index 3 → 40

Since:

20 < 40

new range becomes:

index 0 to 2

Next middle:

index 1 → 20

Found।

Practice 5 — Complexity

Linear Search worst case?

Answer

O(n)

Practice 6 — Complexity

Binary Search worst case?

Answer

O(log n)

Practice 7 — Requirement

Can Binary Search correctly operate on arbitrary unsorted input?

Answer

No।

The algorithm depends on sorted ordering to eliminate half of the remaining candidates।

Practice 8 — Arrays.binarySearch()

Given:

int[] numbers = {
        10,
        20,
        30,
        40
};

write a membership check for 30।

Solution

boolean found =
        Arrays.binarySearch(
                numbers,
                30
        ) >= 0;

Practice 9 — Missing Result

Given:

int[] numbers = {
        10,
        20,
        40,
        50
};

search for 30।

Insertion point is:

2

What encoded result does Arrays.binarySearch() use?

Answer

Formula:

-(insertionPoint) - 1

So:

-2 - 1
= -3

Practice 10 — One Search

You have an unsorted array of one million elements and need exactly one search।

Which is more directly appropriate?

Sort + Binary Search
or
Linear Search

Answer

Usually:

Linear Search

because sorting first costs more than simply scanning once।

Practice 11 — Many Searches

You have a stable sorted dataset of one million elements and expect many thousands of searches।

Which is a strong choice?

Answer

Binary Search

because each lookup is:

O(log n)

Practice 12 — Frequent Membership

Ordering does not matter and you have frequent lookups by exact value।

What structure may be better than both array search strategies?

Answer

Often:

HashSet

with typical average membership lookup:

O(1)

True or False

  1. Linear Search requires sorted input.
  2. Linear Search worst-case time is O(n).
  3. Binary Search requires ordered data.
  4. Binary Search repeatedly reduces the search range.
  5. Binary Search worst-case time is O(log n).
  6. left <= right allows checking a final single candidate.
  7. When middle value is less than the target, search should continue on the left.
  8. Arrays.binarySearch() returns a negative value when the target is missing.
  9. A missing Binary Search result is always exactly -1.
  10. Sorting before one search is always better than Linear Search.
  11. Binary Search can return any matching occurrence when duplicates exist.
  12. Hash-based lookup may be more appropriate when ordering is irrelevant and membership checks are frequent.

Answers

1. False
2. True
3. True
4. True
5. True
6. True
7. False
8. True
9. False
10. False
11. True
12. True

Knowledge Check

Question 1

How does Linear Search work?

Question 2

What is Linear Search's worst-case complexity?

Question 3

Why does Binary Search require sorted data?

Question 4

What do left and right represent?

Question 5

How is the middle index calculated safely?

Question 6

What happens when the middle value is smaller than the target?

Question 7

Why does Binary Search have O(log n) complexity?

Question 8

What does a negative Arrays.binarySearch() result mean?

Question 9

When is Linear Search often preferable to sorting and then using Binary Search?

Question 10

When does Binary Search become particularly useful?

Question 11

Why might a HashSet be better for some search requirements?

Question 12

What happens with duplicate values in a normal Binary Search?

Knowledge Check Answers

Answer 1

Linear Search checks elements sequentially until the target is found or there are no elements left।

Answer 2

O(n)

Answer 3

Sorted ordering allows the algorithm to determine that an entire half of the remaining values cannot contain the target।

Answer 4

They represent the current inclusive search boundaries।

Answer 5

int middle =
        left
        + (
                right - left
        ) / 2;

Answer 6

The target, if present, must be on the right side, so:

left =
        middle + 1;

Answer 7

Because every iteration discards roughly half of the remaining search space।

Answer 8

The target was not found. The negative value also encodes the insertion point that would preserve sorted order।

Answer 9

When the input is unsorted and only one or a small number of searches are required।

Answer 10

When the data is already sorted or can remain sorted and many searches need to be performed efficiently।

Answer 11

A HashSet offers typical average O(1) membership checks and does not require sorted ordering, at the cost of additional memory and different ordering semantics।

Answer 12

It can return a matching index, but a normal Binary Search does not necessarily guarantee the first or last matching occurrence।

Search Strategy Checklist

Before choosing a search algorithm, ask:

Is the data sorted?

Does original order matter?

How many searches will happen?

How often does the data change?

Do I need the index?

Do I need the first duplicate?

Do I only need existence?

Would a Set solve the problem better?

Would a Map keyed by ID be more appropriate?

Do not choose Binary Search simply because:

O(log n) sounds faster.

The surrounding data lifecycle matters।

Search Strategy Summary

Linear Search

Sorted data required?
No

Worst-case time:
O(n)

Extra space:
O(1)

Good for:
Small data
Unsorted data
One-off searches
Simple sequential lookup

Binary Search

Sorted data required?
Yes

Worst-case time:
O(log n)

Extra space:
O(1) iterative

Good for:
Large sorted data
Repeated searches
Ordered datasets
Boundary lookup problems

Hash-Based Search

Sorted data required?
No

Typical membership:
Average O(1)

Extra space:
O(n)

Good for:
Frequent exact membership lookup
Key-based lookup
When ordering is not the main requirement

Lesson Summary

এই lesson-এ আমরা two fundamental search strategies শিখেছি।

We learned:

  • Search can return existence, position, or a matching object
  • Linear Search checks values sequentially
  • Linear Search works with unsorted data
  • Linear Search worst-case time is O(n)
  • Binary Search requires sorted data
  • Binary Search uses left, right, and middle
  • Each Binary Search step discards roughly half the search space
  • Iterative Binary Search has O(log n) time and O(1) extra space
  • Recursive Binary Search uses O(log n) call-stack space
  • Arrays.binarySearch() provides standard array Binary Search
  • Collections.binarySearch() provides Binary Search for sorted lists
  • Missing standard-library Binary Search results are negative and encode insertion position
  • Duplicate values require modified logic when first or last occurrence matters
  • Sorting before a single search is often unnecessary
  • Sorting once may make sense for many repeated searches
  • Sorting changes array order unless a copy is made
  • A HashSet or HashMap may be a better choice for frequent exact lookup
  • Search algorithm selection depends on the whole data-access pattern, not Big-O alone

The central comparison is:

Linear Search
→ inspect values one by one
→ O(n)

Binary Search
→ discard half repeatedly
→ O(log n)
→ requires sorted data

And the engineering question is not simply:

Which algorithm is theoretically faster?

It is:

Which data structure and search strategy
fit this application's access pattern?

Next Lesson

পরবর্তী lesson:

Simple Sorting Algorithms

আমরা শিখব:

  • What sorting means
  • Why sorted data is useful
  • Comparison and swapping
  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Step-by-step execution
  • O(n²) complexity
  • Best and worst-case behavior
  • In-place sorting
  • Stability intuition
  • Why these algorithms matter even though Java provides Arrays.sort()