题解 | #二分查找-II#
二分查找-II
http://www.nowcoder.com/practice/4f470d1d3b734f8aaf2afb014185b395
一、暴力遍历
这道题给的数据不会超时,但正常情况下时间复杂度太高。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 如果目标值存在返回下标,否则返回 -1 * @param nums int整型vector * @param target int整型 * @return int整型 */ int search(vector<int>& nums, int target) { // write code here int n = nums.size(); for(int i = 0; i < n; i++){ if(nums[i] == target) return i; } return -1; } };
二、二分查找
能用迭代搜索的问题一般都可以用二分搜索解,注意此处需要搜索第一次出现的值,所以在搜索到值后需要缩小右侧边界,以锁定第一次出现的值。
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 如果目标值存在返回下标,否则返回 -1 * @param nums int整型vector * @param target int整型 * @return int整型 */ int search(vector<int>& nums, int target) { // write code here int n = nums.size(); int l = 0; int r = n; while(l < r){ //防止数据溢出 int mid = l + (r - l) / 2; if(nums[mid] == target) r = mid; else if(nums[mid] < target) l = mid + 1; else if(nums[mid] > target) r = mid; } if (l >= n || nums[l] != target) return -1; return l; } };