Searching algorithms: linear and binary search

Học bằng cách chơi

Trả lời những câu hỏi này để kiếm năng lượng, rồi câu cá và khám phá. Không cần tài khoản.

Dành cho nhà giáo dục: slide bài học, ghi chú ôn tập sẵn dùng cho Searching algorithms: linear and binary search (KS3 Computing, Computer Science) — dùng trong bài giảng của bạn, hoặc chạy chủ đề như một hoạt động lớp học tương tác để người học chơi như một trò chơi trực tiếp.

Ghi chú bài học

Introduction to Search Algorithms

A search algorithm finds the position of a target value within a list of items.
Two common search algorithms are linear search and binary search.
Linear search checks each item in order until the target is found or the list ends.
Binary search repeatedly divides a sorted list in half to locate the target.
The choice of algorithm affects speed and efficiency, especially with large data sets.

Linear Search

Linear search starts at the first element and compares each element with the target.
It works on unsorted or sorted lists.
In the worst case, it checks every element, so it takes n comparisons for a list of n items.
Its time complexity is O(n) – linear time.
It is simple to implement but slow for large lists.
Best used when the list is small or unsorted.

Binary Search

Binary search requires the list to be sorted in ascending order.
It compares the target with the middle element of the list.
If the target is less than the middle, the search continues in the left half; if greater, in the right half.
This process repeats, halving the search area each time.
If the search area becomes empty, the target is not present.
It runs in O(log n) time – logarithmic time.
For a list of 1,000,000 items, binary search needs at most about 20 comparisons, while linear search may need up to 1,000,000.

Binary Search Step-by-Step

Set low to 0 and high to n-1 (the first and last indices).
While low ≤ high, calculate mid = (low + high) / 2 (rounded down).
If the middle element equals the target, return mid.
If the middle element is less than the target, set low = mid + 1.
If the middle element is greater than the target, set high = mid - 1.
If low > high, the target is not found.

Comparing Efficiency

Linear search time grows proportionally with list size (O(n)).
Binary search time grows logarithmically (O(log n)).
For small lists, linear search may be faster due to less overhead.
For large sorted lists, binary search is dramatically faster.
Binary search requires the list to be sorted, which adds an initial cost if not already sorted.

When to Use Each Algorithm

Use linear search when the list is unsorted or small.
Use linear search when you need to find all occurrences of a value.
Use binary search when the list is sorted and large.
Use binary search when you need the fastest search time.
If the list is frequently updated, sorting overhead may make linear search more practical.

Key Terms

Array – a collection of items stored at contiguous memory locations.
Sorted – arranged in ascending or descending order.
Target – the value being searched for.
Index – the position of an element in an array (starting at 0).
Time complexity – a measure of how the running time grows with input size.
O(n) – linear time; O(log n) – logarithmic time.

Common Mistakes

Forgetting to sort the list before using binary search.
Using mid = (low + high) / 2 without rounding down (integer division).
Not updating low or high correctly, causing infinite loops.
Assuming binary search works on unsorted data.
Confusing index with value when comparing.

Slide

Step through every slide for this topic — plus flashcards and revision notes — with a free account.

ĐĂNG KÝ — MIỄN PHÍ ĐĂNG NHẬP

Câu hỏi luyện tập

Xem trước miễn phí — 8 trên 59 câu hỏi. Đăng ký để xem tất cả.

1.What is the main requirement for binary search to work correctly?
Easy
- AThe data must be sorted
- BThe data must be unsorted
- CThe data must be stored in a hash table
- DThe data must be small
2.Linear search requires the data to be sorted.
Easy
True or false?
3.Which search algorithm is generally faster on a large sorted list?
Easy
- ABinary search
- BLinear search
- CBoth are equally fast
- DIt depends on the programming language
4.Arrange the steps of a binary search on a sorted array in the correct order:
Easy
- Compare the target with the middle element.
- If the target is less than the middle, search the lower half.
- If the target is greater than the middle, search the upper half.
- If the target equals the middle, return its position.
5.Which of the following are true about linear search? (Select all that apply)
Easy
- AIt checks each element in order.
- BIt requires the data to be sorted.
- CIt works on unsorted data.
- DIt is usually slower than binary search on large lists.
- EIt always starts from the middle of the list.
6.Given the sorted list [2, 5, 8, 12, 16, 23, 38], what is the first element compared to when searching for 23 using binary search?
Medium
- A12
- B16
- C23
- D38
7.In binary search, after comparing the target to the middle element and finding it is greater, what happens next?
Medium
- AThe lower half is eliminated and the search continues in the upper half.
- BThe upper half is eliminated and the search continues in the lower half.
- CThe search stops immediately.
- DThe entire list is searched again.
8.Binary search can be used on an unsorted list if you first sort it.
Easy
True or false?

Thêm câu hỏi

9.Match each search algorithm to its key characteristic.
Easy
- Linear search
- Binary search
- Works on unsorted data
- Requires sorted data
- Eliminates half the data each step
- Compares each element in turn
10.Put the steps of a binary search on a sorted array in the correct order.
Medium
- Compare the target with the middle element.
- If the target is greater, search the upper half.
- If the target is less, search the lower half.
- Repeat until found or the remaining half is empty.
11.Which of the following are true about binary search? (Select all that apply)
Medium
- AIt requires the data to be sorted.
- BIt compares the target with the middle element first.
- CIt works on linked lists as efficiently as on arrays.
- DIts worst-case time is O(log n).
- EIt always finds the target in fewer comparisons than linear search.
12.Given the sorted list [2, 5, 8, 12, 16, 23, 38], which element is compared first when searching for 23 using binary search?
Medium
- A12
- B16
- C23
- D38
13.Which search algorithm works on data that is not sorted?
Medium
- ALinear search
- BBinary search
- CHalf-interval search
- DLogarithmic search
14.A list contains 1000 sorted numbers. Approximately how many comparisons would binary search make in the worst case?
Medium
- A10
- B100
- C500
- D1000
15.A student has a list of 10 unsorted numbers. Which search algorithm can be used without sorting the list first?
Easy
- ALinear search
- BBinary search
- CBoth linear and binary search
- DNeither linear nor binary search
16.Consider the sorted list [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]. If you are searching for the value 17 using binary search, what is the first element that will be compared?
Medium
- A11
- B9
- C15
- D17
17.Which of the following statements about linear search are correct? (Select all that apply)
Medium
- AIt can be used on unsorted data.
- BIt is always faster than binary search on large sorted lists.
- CIt checks each element in order until the target is found or the list ends.
- DIt has a worst-case time complexity of O(n).
18.Arrange the steps of a binary search on a sorted array in the correct order.
Medium
- Compare the target to the middle element.
- If the target is greater, search the upper half; if less, search the lower half.
- If the target matches, return the index.
- If the remaining half is empty, the target is not present.
19.A phone directory contains 1,000,000 names sorted alphabetically. Using binary search, what is the maximum number of name comparisons needed to find a specific name?
Hard
- A20
- B100
- C1000
- D1,000,000
20.A student has a list of 10,000 unsorted numbers. Which search algorithm can be used to find a specific number without sorting the list first?
Medium
- ALinear search
- BBinary search
- CBoth linear and binary search
- DNeither linear nor binary search
21.What is the first element compared to when searching for 23 using binary search?
Medium
- A12
- B16
- C23
- D38
22.After the first comparison, which half of the list will be searched next?
Medium
- ALeft half
- BRight half
- CBoth halves
- DNone, the search ends
23.A student wants to search for a value in a list that is already sorted. Which algorithm would be the most efficient for a very large list?
Medium
- ALinear search
- BBinary search
- CBoth are equally efficient
- DNeither can be used
24.Which search algorithm requires the data to be sorted before it can be used?
Easy
- ABinary search
- BLinear search
- CBoth
- DNeither
25.What is another name for binary search?
Easy
- AHalf-interval search
- BSequential search
- CBrute-force search
- DExponential search
26.Linear search can be used on both sorted and unsorted lists.
Easy
True or false?
27.Binary search is faster than linear search for all array sizes.
Easy
True or false?
28.In binary search, what is the first step after setting the left boundary L to 0 and the right boundary R to n-1?
Easy
- ACheck if L > R
- BCompare the target with the middle element
- CSet the middle position m
- DReturn the position if found
29.Match each search algorithm to its requirement or characteristic.
Easy
- Linear search
- Binary search
- Works on unsorted data
- Requires sorted data
- Uses divide and conquer
- Checks every element
30.After the first comparison in the previous question (searching for 23 in [2, 5, 8, 12, 16, 23, 38]), which half of the list will be searched next?
Medium
- AThe upper half
- BThe lower half
- CThe whole list
- DNone – it is found
31.A student has a list of 5000 unsorted numbers. They need to find a specific number. Which algorithm would be the most appropriate to use without sorting the list first?
Medium
- ALinear search
- BBinary search
- CHash table search
- DExponential search
32.A sorted list contains 1,000,000 names. Using binary search, what is the maximum number of comparisons needed to find a specific name?
Medium
- A20
- B1,000,000
- C500,000
- D10
33.Consider the sorted list [3, 7, 12, 18, 25, 33, 41, 56]. When searching for 33 using binary search, what is the first element compared?
Medium
- A18
- B25
- C33
- D41
34.A sorted array contains 1024 elements. In the worst case, how many comparisons does binary search make?
Hard
- A10
- B11
- C1024
- D512
35.Linear search is always slower than binary search on a sorted list of 10 elements.
Easy
True or false?
36.A student wants to find a specific book in a library by title. The books are arranged alphabetically by title on the shelves. Which search algorithm would be the most efficient and why?
Medium
- ABinary search, because the books are sorted and it eliminates half the remaining books each step.
- BLinear search, because it checks every book until the title is found.
- CBinary search, because it works on unsorted data.
- DLinear search, because it is always faster than binary search.
37.A list of numbers is sorted in ascending order. You perform a binary search for the number 17. After the first comparison, the middle element is 12. What is the next step?
Medium
- ASearch the upper half, because 17 > 12.
- BSearch the lower half, because 17 > 12.
- CSearch the upper half, because 17 < 12.
- DTerminate the search, because 17 is not in the list.
38.Which of the following statements about binary search are true? (Select all that apply)
Hard
- AIt requires the data to be sorted.
- BIt works by repeatedly dividing the search interval in half.
- CIt can be used on unsorted data if you first sort it.
- DIt always finds the target in fewer comparisons than linear search for any list size.
- EIt has a worst-case time complexity of O(log n).
39.What is the other name for binary search?
Easy
- AHalf-interval search
- BLinear search
- CSequential search
- DJump search
40.Which of the following is a requirement for binary search to work correctly?
Easy
- AThe data must be sorted
- BThe data must be unsorted
- CThe data must be stored in a hash table
- DThe data must be small
41.Fill in the blank: Binary search is also known as half-interval search or ___ search.
Easy
Binary search is also known as half-interval search or ____ search.
42.How many comparisons are needed in the worst case to find a value in a sorted list of 16 elements using binary search?
Medium
43.State the time complexity of binary search in the worst case using Big O notation.
Medium
44.In the worst case, how many comparisons does binary search make to find a value in a sorted list of 16 elements?
Medium
45.Complete the sentence.
Easy
Linear search is also called ____ search.
46.A sorted list contains 1,000,000 elements. In the worst case, how many comparisons does binary search make?
Medium
47.Complete the sentence:
Easy
Binary search is also known as half-interval search, logarithmic search, or ____ search.
48.A sorted list contains 8 elements. In the worst case, how many comparisons does binary search make?
Easy
49.Fill in the blank: Binary search is also known as half-interval search, logarithmic search, or ___ search.
Easy
Binary search is also known as half-interval search, logarithmic search, or ____ search.
50.What is the main disadvantage of using binary search compared to linear search?
Medium
51.A sorted array contains 1,000,000 elements. In the worst case, how many comparisons does binary search make? (Give your answer as a whole number.)
Medium
52.Complete the sentence: In binary search, after comparing the target to the middle element, if the target is greater, the search continues in the ___ half of the array.
Easy
In binary search, after comparing the target to the middle element, if the target is greater, the search continues in the ____ half of the array.
53.Explain why binary search is generally faster than linear search for large, sorted lists.
Hard
54.Explain the main advantage of binary search over linear search.
Medium
55.How many comparisons are needed in the worst case to find a value in a sorted list of 16 elements using binary search?
Medium
- A4
- B3
- C6
- D5
56.In the worst case, how many comparisons does binary search make to find a value in a sorted list of 16 elements?
Medium
- A4 comparisons
- B6 comparisons
- C5 comparisons
- D3 comparisons
57.A sorted list contains 1,000,000 elements. In the worst case, how many comparisons does binary search make?
Medium
- A20 comparisons
- B18 comparisons
- C24 comparisons
- D22 comparisons
58.A sorted list contains 8 elements. In the worst case, how many comparisons does binary search make?
Easy
- A3
- B6
- C5
- D4
59.A sorted array contains 1,000,000 elements. In the worst case, how many comparisons does binary search make? (Give your answer as a whole number.)
Medium
- A18
- B24
- C20
- D22

Ghi chú ôn tập

## Searching Algorithms: Linear & Binary Search ### Linear Search - **What it is**: Checks each item in a list one by one until the target is found or the list ends. - **Works on**: Any list, sorted or unsorted. - **Steps**: Start at the first item, compare with target, if not match move to next, repeat. - **Time**: Worst case, it checks every item, so for a list of n items it takes up to n steps (O(n)). - **When to use**: Small lists or when data is unsorted. ### Binary Search - **What it is**: A fast search that repeatedly halves the search area. - **Requirement**: The list must be **sorted** (ascending order). - **How it works**: 1. Compare target with the middle element. 2. If equal, done. 3. If target < middle, search the left half. 4. If target > middle, search the right half. 5. Repeat until found or the search area is empty. - **Time**: Each step halves the list, so it takes at most log₂(n) steps (O(log n)). Much faster than linear search for large lists. - **When to use**: Large sorted lists where speed matters. ### Comparison - **Speed**: Binary search is faster than linear search except for very small arrays. - **Trade-off**: Binary search requires the list to be sorted first, which costs time if not already sorted. - **Example**: For 1,000,000 items, linear search may take 1,000,000 steps; binary search takes at most 20 steps (since 2^20 ≈ 1,000,000). ### Key Points to Remember - Always check if the list is sorted before using binary search. - Binary search eliminates half the remaining items each step. - Linear search is simple but slow for large lists. - Choose the algorithm based on data size and whether data is sorted.

Linear search: A search algorithm that checks each element in a list sequentially until the target is found or the list ends.
Binary search: A search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.
Sorted array: An array where elements are arranged in a specific order, typically ascending (e.g., A0 ≤ A1 ≤ ... ≤ An-1).
Time complexity: A measure of how the number of steps an algorithm takes grows with the size of the input. Linear search is O(n), binary search is O(log n).
O(n): Big O notation indicating that the time grows linearly with the number of elements n.
O(log n): Big O notation indicating that the time grows logarithmically with the number of elements n, meaning each step halves the search space.

Thẻ ghi nhớ

What is a linear search?

A linear search checks each element in a list one by one from the start until the target is found or the list ends. It does not require the list to be sorted.

What is a binary search?

Binary search is an algorithm that finds a target value in a sorted array by repeatedly dividing the search interval in half. It compares the target to the middle element and eliminates half of the remaining elements each step.

What condition must be true for a binary search to work?

The array must be sorted in ascending order (or descending, depending on implementation) before binary search can be applied.

Describe the first step of a binary search on a sorted array.

Compare the target value to the middle element of the array. If they match, return the position. If not, decide which half to continue searching in based on whether the target is less or greater than the middle element.

In binary search, if the target is less than the middle element, which half is searched next?

The lower half (elements with indices less than the middle index) is searched next.

In binary search, if the target is greater than the middle element, which half is searched next?

The upper half (elements with indices greater than the middle index) is searched next.

What happens if the search interval becomes empty in binary search?

If the remaining half is empty, the target is not in the array, and the search terminates as unsuccessful.

What is the time complexity of binary search in the worst case?

Binary search runs in logarithmic time, O(log n), where n is the number of elements in the array.

How does the number of steps in binary search grow as the size of the sorted array doubles?

The number of steps increases by only 1 (since log2(2n) = log2(n) + 1). For example, searching 8 elements takes at most 3 steps, and 16 elements takes at most 4 steps.

How does the number of steps in linear search grow as the size of the list doubles?

The maximum number of steps doubles as well, because linear search may need to check every element. So if a list has n elements, worst-case steps are n.

Which search algorithm is faster for large sorted arrays: linear or binary?

Binary search is faster for large sorted arrays because it has O(log n) time complexity compared to linear search's O(n).

When might linear search be preferred over binary search?

Linear search is preferred for small arrays or when the data is unsorted, because binary search requires the array to be sorted first.

What is the main disadvantage of binary search compared to linear search?

The main disadvantage is that binary search requires the array to be sorted, which may add extra cost if the data changes frequently.

Define the term 'logarithmic time' in the context of binary search.

Logarithmic time means the number of operations grows proportionally to the logarithm of the input size. For binary search, the worst-case number of comparisons is O(log n).

What does the variable 'm' represent in the binary search algorithm?

'm' is the index of the middle element of the current search interval, calculated as L + floor((R - L) / 2).

In the binary search procedure, what are the initial values of L and R?

L is set to 0 (the first index) and R is set to n-1 (the last index), where n is the number of elements in the array.

What is the termination condition for an unsuccessful binary search?

The search terminates unsuccessfully when L > R, meaning the search interval is empty.

Give an example of a binary search on a sorted array of 5 elements: [2, 5, 8, 12, 16], searching for 12. Show the steps.

Step 1: L=0, R=4, m=2 (value 8). 8 < 12, so L=3. Step 2: L=3, R=4, m=3 (value 12). 12 == 12, return index 3.

What is the maximum number of comparisons needed to find an element in a sorted array of 1,000,000 elements using binary search?

At most about 20 comparisons, because log2(1,000,000) ≈ 19.93, so the worst case is 20 comparisons.

What does 'half-interval search' mean?

It is another name for binary search, because each step eliminates half of the remaining search interval.

What is the time complexity of linear search in the worst case?

Linear search has a worst-case time complexity of O(n), where n is the number of elements, because it may need to check every element.

Why is binary search not suitable for unsorted data?

Because binary search relies on the order of elements to decide which half to discard. If the data is unsorted, the middle element gives no reliable information about which half contains the target.

What is the key difference between linear and binary search in terms of data requirement?

Linear search works on any list, sorted or unsorted, while binary search requires the list to be sorted.

If you have a sorted array of 100 elements, what is the maximum number of steps binary search will take?

At most 7 steps, because log2(100) ≈ 6.64, so the worst case is 7 comparisons.

Unlock all 59 questions, flashcards & more

Tạo tài khoản miễn phí để xem mọi câu hỏi, slide, thẻ ghi nhớ và ghi chú ôn tập cho chủ đề này.

ĐĂNG KÝ — MIỄN PHÍ ĐĂNG NHẬP

Đề thi cũ

Luyện đề thi cũ cho chủ đề này sắp ra mắt.

Sắp ra mắt