二分查找很多人都不陌生，它能高效的查找顺序数组里的特定值所在的位置。但有多少人能清楚地说出二分查找区间缩小过程中的边界要不要-1，while循环条件要不要加=号，二分查找有几种写法。 今天，我们就详细讲讲二分查找，让更多人弄清楚二分查找的正确写法。

易错点：边界处理

举个例子：假设下图（查找区间为左闭右开区间）想要查找4，当发现arr[mid] > 4时错将end转移到mid-1处，这样一来查找区间变为[0,4),不管怎么找都找不到4了，就会造成bug。 既然了解了错误原因，解决问题就变得简单了起来，根本上就是要重视边界处理，什么时候要加一什么时候要减一，还有跳出循环的条件中要不要等号，这些都一定要搞清楚。

示例

以下是二分查找（折半查找）的两种正确写法。大家可以作为参考。

//左闭右闭区间 int BinarySearch1(int* a, int n, int x) { assert(a); int begin = 0; int end = n - 1; while (begin <= end) { int mid = begin + ((end - begin) >> 1);//防溢出，>>运算符优先级很低，要再加一个括号 if (a[mid] < x) begin = mid + 1; else if (a[mid] > x) end = mid - 1; else return mid; } return -1; } //左闭右开区间 int BinarySearch2(int* a, int n, int x) { assert(a); int begin = 0; int end = n; while (begin < end) { int mid = begin + ((end - begin) >> 1);//防溢出，>>运算符优先级很低，要再加一个括号 if (a[mid] < x) begin = mid + 1; else if (a[mid] > x) end = mid; else return mid; } return -1; }

细节要记得处理到位，大家加油！

---

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。