The following binary search algorithm will continue searching untile the values

Question

The following binary search algorithm will continue searching untile the values low and high meet, even if by chance the element being targeted is discovered sooner. For example, if we were searching the vector of names for the vlaue "Alex" we would discover the element on the first comparison. Modify the algorithm so that is will halt if the element is discovered.

template<class Iterator, class ValueType>

Iterator lower_bound(Iterator start, Iterator stop, ValueType & value)

{

unsigned int low=0;

unsigned int max = stop - start;

unsigned int high = max;

while(low < high) {

unsigned int mid = (low + high) /2;

if(start[mid] < value)

low = mid +1;

else

high = mid;

}

if (low < max)

return start + low;

return stop;

}

Explanation / Answer

template<class Iterator, class ValueType>
Iterator lower_bound(Iterator start, Iterator stop, ValueType & value)
{
unsigned int low=0;
unsigned int max = stop - start;
unsigned int high = max;
  
while(low < high) {
unsigned int mid = (low + high) /2;
   if (start[mid] == value) return midpoint;
if(start[mid] < value)
low = mid +1;
else
high = mid;
}

if (low < max)
return start + low;
return stop;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.