title: 每日一练（24）：在排序数组中查找数字
categories:[剑指 offer]
tags:[每日一练]
date: 2022/02/23
每日一练（24）：在排序数组中查找数字
统计一个数字在排序数组中呈现的次数。
示例 1:
输出: nums = [5,7,7,8,8,10], target = 8
输入: 2
示例 2:
输出: nums = [5,7,7,8,8,10], target = 6
输入: 0
提醒：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递加数组
-109 <= target <= 109
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
办法一：STL（一行搞定）
count 函数能够用来统计字符串中某个字符的个数
应用办法是 count(ivec.begin() , ivec.end() , searchValue)，其中 begin 指的是起始地址，end 指的是完结地址，第三个参数指的是须要查找的字符。
int search(vector<int>& nums, int target) {return count(nums.begin(),nums.end(),target);
}办法二：暴力解法
间接 for 循环遍历查找指标并计数
int search(vector<int>& nums, int target) {if (nums.size() == 0) {return 0;}
if (nums.size() == 1) {if (nums[0] == target) {return 1;} else {return 0;}
}
int count = 0;
for (int i = 0; i < nums.size(); i++) {if (nums[i] == target) {count++; // 循环计数}
}
return count;
}办法三：二分查找
二分模板：
模板 1
当咱们将区间 [l, r] 划分成 [l, mid] 和[mid + 1, r]时，其更新操作是 r = mid 或者 l = mid + 1，计算 mid 时不须要加 1，即 mid = (l + r)/2。
int bsearch_1(int l, int r)
{while (l < r)
{int mid = (l + r)/2;
if (check(mid)) {r = mid;} else {l = mid + 1;}
}
return l;
}模板 2
当咱们将区间 [l, r] 划分成 [l, mid – 1] 和[mid, r]时，其更新操作是 r = mid – 1 或者 l = mid，此时为了避免死循环，计算 mid 时须要加 1，即 mid = (l + r + 1) /2。
int bsearch_2(int l, int r)
{while (l < r)
{int mid = ( l + r + 1) /2;
if (check(mid)) {l = mid;} else {r = mid - 1;}
}
return l;
}lowerBound(target)upper(target+1)
工夫复杂度剖析： 两次二分查找的工夫复杂度为 O(logn)。
空间复杂度剖析： 没有应用额定的数组，因而空间复杂度为 O(1)。
int lowerBound(vector<int>& nums, int target) {
int l, r;
l = 0;
r = nums.size();
while (l < r) {int mid = (l + r) >> 1;
if (target <= nums[mid]) {r = mid;} else {l = mid + 1;}
}
return l;
}
int search(vector<int>& nums, int target) {int lower = lowerBound(nums, target);
int upper = lowerBound(nums, target + 1);
return (upper - lower);
}