二分查找法详解（6种变形）

前言 在之前的博客中，我给大家介绍了最基础的二分查找法（没学的话点我点我！）

今天我将带大家学习二分法的六种变形如何使用，小伙伴们，快来开始今天的学习吧！

文章目录 1，查找第一个（从左到右）= 目标值的，若不存在返回 -12，查找第一个 >= 目标值的3，查找第一个 > 目标值的4，查找最后一个 = 目标值的 ，若不存在返回- 15，查找最后一个 <= 目标值的6，查找最后一个 < 目标值的总结

1，查找第一个（从左到右）= 目标值的，若不存在返回 -1

与原版二分法其实差不多，当一个数组中有重复的目标值时，使用该方法可以找到从左到右第一个等于目标值的下标。 因为我们要找的是第一个等于目标值的下标，那我们不仅仅在arr[mid] > key时去左边找，在arr[mid]>= key我们也要去找，因为我们需要要最左边等于目标值的下标。 注意事项 最后我们要判断left是否越界(left 有可能等于数组元素的个数)，而且最后arr[left]是否等于要找的key。 代码：

int efcz(int* arr, int key,int left,int right) { int len = right+1;//数组长度（元素个数） int mid = (left + right) / 2; while (left <= right) { mid = (left + right) / 2; if (arr[mid] >= key) { right = mid - 1; } if (arr[mid] < key) { left = mid + 1; } } if (left < len&&arr[left] != key)//判断一下是否找到元素 return -1; else return left; } int main() { int arr[10] = { 1,2,3,5,5,5,5,5,5,6 };//创建数组 int key = 5;//目标值为5 int left = 0;//设置左右起点 int right = sizeof(arr) / sizeof(arr[0]); printf("%d", efcz(arr, key,left,right));//进入二分查找函数 return 0; } 2，查找第一个 >= 目标值的

这次我们需要查找第一个大于等于目标值的下标，这次我们不需要判断left越界，如果越界就说明没有找到，说明整个数组都比目标值要小。 代码：

//思路和第一种一样，我就不加注释了，如果不懂可以私信问我 int efcz(int* arr, int key, int left, int right) { int mid = (left + right) / 2; while (left <= right) { mid = (left + right) / 2; if (arr[mid] >= key) { right = mid - 1; } if (arr[mid] < key) { left = mid + 1; } } return left; } int main() { int arr[10] = { 1,2,3,5,5,5,5,5,6,8 }; int key = 7; int left = 0; int right = sizeof(arr) / sizeof(arr[0]); printf("%d", efcz(arr, key, left, right)); return 0; } 3，查找第一个 > 目标值的

这次我们需要查找第一个大于目标值的下标，这次我们同样不需要判断left越界，如果越界就说明没有找到，说明整个数组都比目标值要小。 另外我们需要改变一下函数内部的判断条件，当arr[mid] <= key时，left = mid + 1 因为我们不是要找相等的，是要找大于目标值的。 代码：

//思路和第一种一样，我就不加注释了，如果不懂可以私信问我 int efcz(int* arr, int key, int left, int right) { int mid = (left + right) / 2; while (left <= right) { mid = (left + right) / 2; if (arr[mid] > key) { right = mid - 1; } if (arr[mid] <= key) { left = mid + 1; } } return left; } int main() { int arr[10] = { 1,2,3,5,5,5,5,5,6,8 }; int key = 5; int left = 0; int right = sizeof(arr) / sizeof(arr[0]); printf("%d", efcz(arr, key, left, right)); return 0; } 4，查找最后一个 = 目标值的 ，若不存在返回- 1

因为我们要找的是第一个等于目标值的下标，那我们不仅仅在arr[mid] < key时去右边找，在arr[mid]>= key我们也要去找，因为我们需要要最右边边等于目标值的下标。 注意事项 最后我们要判断right是否越界(right 有可能等于-1)，而且最后arr[right]是否等于要找的key。 代码：

//思路和第一种一样，我就不加注释了，如果不懂可以私信问我 int efcz(int* arr, int key, int left, int right) { int mid = (left + right) / 2; while (left <= right) { mid = (left + right) / 2; if (arr[mid] > key) { right = mid - 1; } if (arr[mid] <= key) { left = mid + 1; } } if (right >= 0 && arr[right] == key)//判断是否找到 return right; else return -1; } int main() { int arr[10] = { 1,2,3,5,5,5,5,5,6,8 }; int key = 5; int left = 0; int right = sizeof(arr) / sizeof(arr[0]); printf("%d", efcz(arr, key, left, right)); return 0; } 5，查找最后一个 <= 目标值的

这次我们需要查找第一个小于等于目标值的下标，这次我们不需要判断right越界，如果越界就说明没有找到，说明整个数组都比目标值要大。 代码：

//思路和第一种一样，我就不加注释了，如果不懂可以私信问我 int efcz(int* arr, int key, int left, int right) { int mid = (left + right) / 2; while (left <= right) { mid = (left + right) / 2; if (arr[mid] > key) { right = mid - 1; } if (arr[mid] <= key) { left = mid + 1; } } return right; } int main() { int arr[10] = { 1,2,3,5,5,5,5,5,6,8 }; int key = 4; int left = 0; int right = sizeof(arr) / sizeof(arr[0]); printf("%d", efcz(arr, key, left, right)); return 0; } 6，查找最后一个 < 目标值的

这次我们需要查找第一个小于目标值的下标，这次我们同样不需要判断right越界，如果越界就说明没有找到，说明整个数组都比目标值要大。 另外我们也需要改变一下函数内部的判断条件，当arr[mid] >= key时，right = mid - 1，因为我们不是要找相等的，是要找小于目标值的。 代码：

//思路和第一种一样，我就不加注释了，如果不懂可以私信问我 int efcz(int* arr, int key, int left, int right) { int mid = (left + right) / 2; while (left <= right) { mid = (left + right) / 2; if (arr[mid] >= key) { right = mid - 1; } if (arr[mid] < key) { left = mid + 1; } } return right; } int main() { int arr[10] = { 1,2,3,5,5,5,5,5,6,8 }; int key = 5; int left = 0; int right = sizeof(arr) / sizeof(arr[0]); printf("%d", efcz(arr, key, left, right)); return 0; } 总结

我认为可以分两组记忆这六种变形，前三组一类，后三组一类，前三组都是返回left，后三组都是返回right，同时我们会发现，第一种和第四种，第二种和第五种，第三种和第六种都十分的相似，所以自己练练就能掌握，而且不容易忘记，本期的分享就到这里，如果觉得博主讲的不错的话，千万不要忘记给博主一个关注，点赞，收藏哦~，小伙伴们，我们下期再见！