Recently, I decided to create my first instructional video on YouTube and after much deliberation, I eventually settled for the binary search (chop) algorithm. I know, it's all been done a thousand times before, but in my experience, most (if not all) tutorials don't really dig deep into the subtle nuances of its various implementations. Specifically, I wanted to cover both standard and reductive approaches, with particular attention given to both duplicate and nearest low/high matches.
So without further ado, the video may be viewed here.
As this is my first attempt at creating a video of any kind, I'd be very grateful for any comments regarding quality and/or content. In particular, I'd be grateful for any feedback regarding the quality of the narration - I decided to use IBM's text-to-speech service (Watson) rather than narrate the video myself.
For posterity, the code used throughout the video is posted below.
Version #1
bool BinarySearch1(int pTarget,
int *pSortedArray,
int pArrayLength) {
int topIndex, bottomIndex, compareIndex;
bottomIndex = 0;
topIndex = pArrayLength - 1;
while (topIndex >= bottomIndex) {
compareIndex = (bottomIndex + topIndex) >> 1;
if (pSortedArray[compareIndex] == pTarget)
return true;
if (pSortedArray[compareIndex] < pTarget)
bottomIndex = compareIndex + 1;
else
topIndex = compareIndex - 1;
}
return false;
}
Version #2
int BinarySearch2(int pTarget,
int *pSortedArray,
int pArrayLength,
bool pNearestLowest) {
int topIndex, bottomIndex, compareIndex;
bottomIndex = 0;
topIndex = pArrayLength - 1;
do {
compareIndex = (bottomIndex + topIndex) >> 1;
if (pSortedArray[compareIndex] == pTarget)
return pSortedArray[compareIndex];
if (pSortedArray[compareIndex] < pTarget)
bottomIndex = compareIndex + 1;
else
topIndex = compareIndex - 1;
} while (topIndex >= bottomIndex);
return (pNearestLowest)
? pSortedArray[topIndex + (topIndex == -1)]
: pSortedArray[bottomIndex - (bottomIndex == pArrayLength)];
}
Version #3
int BinarySearch3(int pTarget,
int *pSortedArray,
int pArrayLength,
bool pNearestLower) {
int topIndex, bottomIndex, compareIndex;
bottomIndex = 0;
topIndex = --pArrayLength;
while (topIndex != bottomIndex) {
compareIndex = (bottomIndex + topIndex) >> 1;
if (pSortedArray[compareIndex] < pTarget)
bottomIndex = compareIndex + 1;
else
topIndex = compareIndex;
}
return (pNearestLower)
? pSortedArray[bottomIndex - ((bottomIndex > 0) &&
(pSortedArray[bottomIndex] > pTarget))]
: pSortedArray[bottomIndex + ((bottomIndex < pArrayLength) &&
(pSortedArray[bottomIndex] < pTarget))];
}
Version #4
int BinarySearch4(int pTarget,
int *pSortedArray,
int pArrayLength,
bool pNearestLower) {
int topIndex, bottomIndex, compareIndex;
bottomIndex = 0;
topIndex = --pArrayLength;
while (topIndex != bottomIndex) {
compareIndex = (bottomIndex + topIndex + 1) >> 1;
if (pSortedArray[compareIndex] > pTarget)
topIndex = compareIndex - 1;
else
bottomIndex = compareIndex;
}
return (pNearestLower)
? pSortedArray[bottomIndex - ((bottomIndex > 0) &&
(pSortedArray[bottomIndex] > pTarget))]
: pSortedArray[bottomIndex + ((bottomIndex < pArrayLength) &&
(pSortedArray[bottomIndex] < pTarget))];
}
Top comments (0)