二分查找模板（binary_search）

大家好啊二分查找是一个很常见的问题也许大家认为很简单但是二分查找毕竟可以分为对于递增不递减数组递减不递增数组查找不大于小于不小于大于共八种情况而我们接触到的库函数upper_bound和lower_bound也仅仅只包含两种情况罢了。如果你常常像我一样为二分查找的条件以及返回值而头昏眼花的话那么就请看看这篇帖子吧如果有错误的话欢迎指正~~~目录一、何为二分查找二、表示二分查找的三种区间选择三、二分查找模板口诀详细代码1递增非递减从小到大数组2递减非递增从大到小数组四、结语一、何为二分查找二分查找一般指的是在一个有序数组中通过不断将搜索范围缩小一半来高效定位某个特定目标值的方法。核心思想分治Divide and Conquer时间复杂度O(nlog n)空间复杂度O(1)。二、表示二分查找的三种区间选择对于二分查找我们需要取一个左值left和一个右值right在区间选择上有三种[left, right],[left, right), (left, right)这三种取法区别在于初始边界设定left和right的取值循环条件while的判断边界更新方式left和right的调整我更习惯使用第一种也就是闭区间[left, right]并且返回值为下标其他两种就不做讲解。三、二分查找模板int binary_search_template(int arr[], int target) { int lefft 0, right arr.size() - 1; while(left right) { int mid left (right - left) / 2; //防止越界 if (/*情况特定条件*/) ...... else ...... } return /*返回值*/ }口诀情况特定条件针对于arr[mid]与target的比较若不大于()小于()不小于()大于()返回值若为第一个要寻找的值则为left若为最后一个要寻找的值则为right需要理解。省略号部分else下面的与返回值统一若返回值为leftelse下则为left mid 1反之。详细代码1递增非递减从小到大数组// 递增数组找不大于target的最大数 int binary_search_1(int nums[], int target) { int left 0, right nums.size()- 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) left mid 1; else right mid - 1; } //一般情况直接返回(不大于target的最后一个数) return right; } // 递增数组找小于target的最大数 int binary_search_2(int nums[], int target) { int left 0, right nums.size()- 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) left mid 1; else right mid - 1; } //一般情况直接返回(小于target的最后一个数) return right; } // 递增数组找不小于target的最小数 int binary_search_3(int nums[], int target) { int left 0, right nums.size()- 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) right mid - 1; else left mid 1; } //一般情况直接返回(不小于target的第一个数) return left; } // 递增数组找大于target的最小数 int binary_search_4(int nums[], int target) { int left 0, right nums.size()- 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) right mid - 1; else left mid 1; } //一般情况直接返回(大于target的第一个数) return left; }2递减非递增从大到小数组// 递减数组找不大于target的最大数 int binary_search_5(int nums[], int target) { int left 0, right nums.size()- 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) right mid - 1; else left mid 1; } //一般直接返回不大于target的第一个数 return left; } // 递减数组找小于target的最大数 int binary_search_5(int nums[], int target) { int left 0, right nums.size()- 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) right mid - 1; else { left mid 1; } //一般直接返回小于target的第一个数 return left; } // 递减数组找不小于target的最小数 int binary_search_5(int nums[], int target) { int left 0, right nums.size()- 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) left mid 1; else right mid - 1; } //一般直接返回不小于target的最后一个数 return right; } // 递减数组找大于target的最小数 int binary_search_5(int nums[], int target) { int left 0, right nums.size()- 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) left mid 1; else right mid - 1; } //一般直接返回大于target的最后一个数 return right; }四、结语本篇仅仅作为模板使用不做其他讲解希望能够帮助大家如果有发现错误请及时指正备注此篇内容均为原创代码是经过较为仔细地学习之后自己总结各路写法得到如果内容有什么错误欢迎指正