二进制搜索（CHOP）算法 - 在C中带有示例
#初学者 #算法 #c #cpp

最近，我决定在YouTube上创建我的第一个教学视频，经过大量审议，我最终定居于二进制搜索（CHOP）算法。我知道，这一切都已经完成了一千次，但是根据我的经验，大多数（如果不是全部）教程并没有真正深入研究其各种实现的微妙细微差别。具体而言，我想涵盖标准和还原方法，特别注意重复和最近的低/高匹配。

因此，如果不进一步的ado，可以查看视频here。

这是我第一次创建任何类型视频的尝试，我非常感谢有关质量和/或内容的任何评论。特别是，我感谢有关叙述质量的任何反馈 - 我决定使用IBM的文本到语音服务（WATSON），而不是自己叙述视频。

对于后代，整个视频中使用的代码在下面发布。

版本＃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;
}

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

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

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