IPA IP 2023 Question 69

Topic: Algorithm and Programming

A question IPA Japan published in 令和5年度 ITパスポート試験 公開問題 問69, translated into English. ITPEC is based on the same exams.

Which of the following is an appropriate description concerning search algorithms when data stored in an array is searched?

Explanation

Linear search takes computation proportional to the number of elements — it compares the elements one by one from the start, so doubling the array doubles the work.

PointLinear searchBinary search
How it searchesFrom the first element, in orderCompares with the middle element and halves the range each time
Order neededNoneSorted in ascending or descending order
Comparisons, n elementsUp to n, on average about n/2Up to about log₂ n + 1

Answer (b)

Why not others:

  • •(a) — searching in order from the first element is linear search; binary search starts at the middle
  • •(c) — it is binary search that needs sorted data; linear search works on data in any order
  • •(d) — binary search is faster on average, but not for every value: if the value sits in the first element, linear search finds it in one comparison while binary search needs several

Key rule: Linear search works on any array in time proportional to n; binary search needs sorted data and takes time proportional to log₂ n.

Algorithm and Programming · AI-written, may contain errors

Practice this exam

This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.