Binary search is such an efficient searching algorithm because during each pass
ID: 653223 • Letter: B
Question
Binary search is such an efficient searching algorithm because during each pass of the loop (in the iterative version) or in each method call (in the recursive version) the size of the list is essentially halved. If reducing the size of the list to be searched by one half is so effective, it may seem that reducing it by two thirds each time would be even more effective. To that end, consider this iterative ternary search method. Rewrite it is as a recursive ternary search method named int recTernarySearch(ArrayList pList, Integer pKey, int pLow, int pHigh).
int ternarySearch(ArrayList pList, Integer pKey) {
int low = 0, high = pList.size() - 1;
while (low <= high) {
int range = high - low;
int + range / 3.0);
int twoThirdIdx = (int)Math.round(low + range / 1.33);
if (pKey.equals(pList.get(oneThirdIdx))) {
return oneThirdIdx;
} else if (pKey.equals(pList.get(twoThirdIdx))) {
return twoThirdIdx;
} else if (pKey < pList.get(oneThirdIdx)) {
high = oneThirdIdx - 1;
} else if (pKey > pList.get(twoThirdIdx)) {
low = twoThirdIdx + 1;
} else {
low = oneThirdIdx + 1;
high = twoThirdIdx - 1;
} } return -1;
Explanation / Answer
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.