Search Algorithms for Arrays in Java - Quiz
Total: 5 questions
1. What is linear search, what is its complexity, and when should you use it?
What is linear search, what is its complexity, and when should you use it?
Linear search iterates over the array elements in order and compares each one with the target value. As soon as a match is found it returns the index; if it reaches the end it returns -1. Its complexity is O(n). It is the only method covered in the lesson that does not require the array to be sorted, so it is a good fit for unsorted arrays and small datasets.
2. Why does binary search only work on a sorted array?
Why does binary search only work on a sorted array?
At each step binary search discards half of the array based on a comparison of the target with the middle element. The conclusion that the target lies to the left or to the right of the middle is only valid when the elements are ordered. On unsorted data discarding half of the array is incorrect, so the algorithm returns a wrong result. The complexity of binary search is O(log n).
3. How does the iterative implementation of binary search differ from the recursive one, and does recursion have any pitfalls?
How does the iterative implementation of binary search differ from the recursive one, and does recursion have any pitfalls?
Both implementations use the same idea — halving the range — and both run in O(log n). The iterative version narrows the firstIndex and lastIndex bounds inside a while loop. The recursive version calls itself for the narrowed range at each step: the code is shorter and the logic is easier to read. The recursion caveat: the JVM does not perform tail-call optimization, so in theory a very deep call tree could cause a StackOverflowError. But since the depth of binary search is only O(log n), in practice this is more of a quirk than a real risk.
4. How does jump search work, what is its complexity, and when is it beneficial?
How does jump search work, what is its complexity, and when is it beneficial?
Jump search works on sorted arrays. The algorithm jumps ahead by a fixed number of elements (usually a step of √n) until it overshoots the target value, then performs a linear search inside the found block. Its complexity is O(sqrt n). It is beneficial on large sorted arrays where a "step back" is more expensive than a "step forward" — for example, when reading data sequentially from a storage medium.
5. Which built-in Java tools let you find an element without implementing an algorithm by hand?
Which built-in Java tools let you find an element without implementing an algorithm by hand?
The standard library already ships proven solutions: Arrays.binarySearch(array, key) performs a binary search over a sorted array and returns the index of the element, or a negative number if it is absent. For collections there are list.indexOf(element) (linear search) and Collections.binarySearch(list, key). To check for presence, the Stream API is handy: IntStream.of(array).anyMatch(x -> x == key). Important: the array passed to Arrays.binarySearch must be sorted beforehand, for example with Arrays.sort(array).