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

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

Qodo Takeover

Introducing Qodo Gen 1.0: Transform Your Workflow with Agentic AI

While many AI coding tools operate as simple command-response systems, Qodo Gen 1.0 represents the next generation: autonomous, multi-step problem-solving agents that work alongside you.

Read full post

Top comments (0)

AWS GenAI LIVE!

GenAI LIVE! is a dynamic live-streamed show exploring how AWS and our partners are helping organizations unlock real value with generative AI.

Tune in to the full event

DEV is partnering to bring live events to the community. Join us or dismiss this billboard if you're not interested. ❤️