牛客NC105-二分查找

题目描述

请实现有重复数字的有序数组的二分查找。

输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。

示例1

输入

5,4,[1,2,4,4,5]

输出

3

思路：

题目输出的是自然顺序而不是索引顺序；

1.递归

相当于是有重复数字的有序数组二分查找基础上，查找最左边的位置，如果当前元素大于等于目标值v，判断它前一个元素是否也大于等于目标值v，如大于则继续二次查找，否则返回该索引位置+1，递归结束条件为查找到或者右边界严格小于左边界。

class Solution { public: /** * 二分查找 * @param n int整型 数组长度 * @param v int整型 查找值 * @param a int整型vector 有序数组 * @return int整型 */ int upper_bound_(int n, int v, vector<int>& a) { // write code here int index = Binary_Search_Left(a, v, 0, n - 1); return index; } int Binary_Search_Left(vector<int> &a, int v, int left, int right){ int n = a.size(); int mid = (left + right) >> 1; if(right < left){ return n+1; } if(a[mid] >= v){ if(mid == 0)//判断是不是最左边 return 1; else if(a[mid-1] >= v)//不是第一个位置 return Binary_Search_Left(a, v, left, mid - 1); else//第一个位置 return mid + 1; } else if(a[mid] < v) return Binary_Search_Left(a, v, mid + 1, right); } };

 2.非递归

思路同上，改为非递归实现

class Solution { public: /** * 二分查找 * @param n int整型 数组长度 * @param v int整型 查找值 * @param a int整型vector 有序数组 * @return int整型 */ int upper_bound_(int n, int v, vector<int>& a) { // write code here if(a.back() < v)//有序数组最后一个值都严格小于v，那么一定不存在 return n + 1; int l = 0, r= n - 1; while(l <= r){ int mid = (l + r) >> 1; if(a[mid] >= v){ if(mid == 0) return 1; else if(a[mid-1] >= v){ r = mid - 1; } else return mid + 1; } else{ l = mid + 1; } } //没找到 return n + 1; } };