C++学习笔记-----二分法之寻找非减序列第一个大于某个值的数或最后一个小于某个值的数

二分法在对有序序列的处理上可以达到O(lg(n))的时间复杂度，通常用在二分查找上。

此时有一个有序序列，给定一个数n，n可以在这个序列中也可以不在，要求找到第一个大于n的数和第一个小于n的数。

实际上，只需要在二分法的基础上稍加改动即可达到需求

二分查找n的下标

int binaryFind(vector<int>& nums, int n) { int left = 0; int right = nums.size() - 1; while(left < right) { int middle = (left + right) / 2; if(nums[middle] > n) right = middle - 1; else if(nums[middle] < n) left = middle + 1; else return middle; } return left; }

二分查找寻找第一个大于n的数的下标

int binaryFindFirstMoreNum(vector<int>& nums, int n) { int left = 0; int right = nums.size() - 1; while(left < right) { int middle = (left + right) / 2; if(nums[middle] > n) right = middle; //保留大于n的下标以防这是第一个 else if(nums[middle] <= n) //将小于改为小于等于 left = middle + 1; } if(nums[left] > n) return left; else return -1; }

二分查找最后一个小于n的数的下标

int binaryFindLastLessNum(vector<int>& nums, int n) { int left = 0; int right = nums.size() - 1; while (left < right) { int middle = (left + right) / 2; if (nums[middle] >= n) //将大于改为大于等于 right = middle - 1; else if (nums[middle] < n) { //避免无限循环 if (left == middle) { if (nums[right] < n) left = right; break; } else { left = middle; //保留小于n的下标以防这是最后一个 } } } /* 循环结束有两种可能 1. break跳出，此时left==right 2. left==right 3. left>right，发生在所有元素都大于n的情况，此时left==0 && right==-1 */ if(nums[left] < n) return left; else return -1; }