DEV Community

Cover image for The Binary Search (Chop) Algorithm - with examples in C
Decrepit Coder
Decrepit Coder

Posted on

The Binary Search (Chop) Algorithm - with examples in C

#c #cpp #algorithms #beginners

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; }
Enter fullscreen mode Exit fullscreen mode

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)]; }
Enter fullscreen mode Exit fullscreen mode

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))]; }
Enter fullscreen mode Exit fullscreen mode

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))]; }
Enter fullscreen mode Exit fullscreen mode

Top comments (0)