搜索数组数据插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。数组可能有重复数据，有重复数据时返回，插入到重复数据的第一个位置。
示例 1: 输入: [1,3,6,7], 5， 输出: 2
示例 1: 输入: [1,3,3,3,5,6], 3， 输出: 1
分析：改进的二分法 。 计算 mid 时需要技巧防止溢出，即 mid=left+(right-left)/2 。二分查找中若在排序数组中查找一个不存在的数x,则最后查找返回的结果right下标对应的值为数组中小于x的最大数, left下标对应的值为数组中大于x的最小数。插入位置为left。
参考链接
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int length = nums.size();
int left = 0;
int right = length-1;
//[3,5,7,9,10] 8 3
while (left <=right) {
int mid = (right + left) / 2; //
if(target > nums[mid])
{
left = mid+1; //
}
else if(target ==nums[mid]){
right=mid-1;
}
else{
right = mid-1; //
}
}
return left;
}
};
在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。
示例 1: 输入: nums = [5,7,7,8,8,10], target = 8。输出: [3,4]
示例 2: 输入: nums = [5,7,7,8,8,10], target = 6。输出: [-1,-1]
分析： 参考链接
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res(2, -1);
if (nums.empty()) return res;
int left = 0, right = nums.size() - 1;
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
}
else if (nums[mid] > target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
}
else if (nums[mid] == target) {
// 收缩右侧边界
right = mid - 1;
}
}
// 检查出界情况
if (left >= nums.size() || nums[left] != target)
return res;
res[0] = left;
//
right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
}
else if (nums[mid] > target) {
right = mid - 1;
}
else if (nums[mid] == target) {
// 这里改成收缩左侧边界即可
left = mid + 1;
}
}
res[1] = right;
return res;
}
};
x 的平方根
实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1: 输入: 4, 输出: 2
示例 2: 输入: 8, 输出: 2 。说明: 8 的平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
分析： 二分查找，找到在1~x中的最大的value*value<=x的value值。二分查找中若在排序数组中查找一个不存在的数x,则最后查找返回的结果right下标对应的值为数组中小于x的最大数, left下标对应的值为数组中大于x的最小数。
class Solution {
public:
int mySqrt(int x) {
int right = x;
int left = 1;
while (left <= right) {//找到mid^2 小于等于x的最大值
int mid = left + (right - left) / 2;
if (x/mid < mid)
right = mid-1;
else if ( mid < x/mid)
left = mid+1;
else
return mid;
}
return right;
}
};
浮点数求立方根
给一个浮点数num, 如何求其立方根ans？
double cubeRoot(double num) {
double left = 0;
double right = num;
if (num < 0) {
left = num;
right = 0;
}
double mid = (left + right) / 2;
double ans = mid* mid *mid;
while (abs(num - (ans)) > 0.00001) {
mid = (left + right) / 2;
ans = mid * mid * mid;
if (ans - num > 0.00001) {
right = mid;
} else if (num - ans > 0.00001){
left = mid;
}
}
return mid;
}
数组中数值和下标相等的元素
假设一个单调递增的数组里的每个元素都是整数并且是唯一的。
请编程实现一个函数找出数组中任意一个数值等于其下标的元素。
例如，在数组[-3, -1, 1, 3, 5]中，数字3和它的下标相等。
样例:
输入：[-3, -1, 1, 3, 5]
输出：3
1
2
注意:如果不存在，则返回-1。
class Solution {
public:
int getNumberSameAsIndex(vector<int>& nums) {
int left = 0;
int right = nums.size();
int mid = -1;
while(right >= left){
mid = left + (right-left) / 2;
if(nums[mid] == mid){
return mid;
}
if(nums[mid] > mid){
right = mid - 1;
}else{
left = mid + 1;
}
}
return -1;
}
};
