The idea of binary search is to cut an array (sorted) into two parts and discard
ID: 3652498 • Letter: T
Question
The idea of binary search is to cut an array (sorted) into two parts and discard the part which could not contain our searching target.// Code for BinarySearch
int BinarySearch(IntArrayType IntArray, int Low, int High, int Target)
{
int Mid, Difference;
while (Low <= High)
{
Mid = (Low + High) / 2;
Difference = IntArray[Mid] - Target;
if (Difference == 0) // IntArray[Mid] == Target
return Mid;
else if (Difference < 0) // IntArray[Mid] < Target
Low = Mid + 1;
else
High = Mid - 1;
}
return -1; // If reach here, Target was not found.
}
Try the Binary Search in action:
cp /net/data/ftp/pub/class/115/ftp/cpp/BinarySearch/BinSearch.h BinSearch.h
cp /net/data/ftp/pub/class/115/ftp/cpp/BinarySearch/BinSearch.cpp BinSearch.cpp
cp /net/data/ftp/pub/class/115/ftp/cpp/BinarySearch/BinMain.cpp BinMain.cpp
Questions
Is the data sorted?
How would you print out the number of times that the Difference is calculated?
Explanation / Answer
a) yes b) add the print command printf(i) in the if,else loop b4 it ends..
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.