We tested it against a linear search implementation that we saw in class earlier
ID: 3820002 • Letter: W
Question
We tested it against a linear search implementation that we saw in class earlier. The code starts by creating an array of a million monotonically increasing values (a subsequent value can differ from its predecessor by 0, 1, or 2). Then, it times searching for 100000 values in that array. We also add up all the indexes where we find what we're looking for along with -1 values when we don't find what we're looking for. Finally, we search for the same values with binarySearch and also add either the found index or -1 if not found.
However, we saw that the indexSum values differed. They don't differ by much, though! Which of these changes to binarySearch will fix it?
A. For the x < y case, instead, return binarySearch(a, x, low, index);Explanation / Answer
C. Instead of if (low > high), change to if (low >= high)
low should always be smaller than y so it should be checked for equality also.If low = high then it also returns -1 because this is also the case of invalid range.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.