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

Decrepit Coder — Thu, 01 Jun 2023 14:31:33 +0000

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))];
}

DEV Community: Decrepit Coder

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