leetcode7二分查找_69 and 34

leetcode学习算法之二分查找：

二分查找也称为二分法或折半查找，二分查找在有序的数组长进行查找，时间复杂度为O(logn).
69.x的平方根
34. 在排序数组中查找元素的第一个和最后一个位置

69.x的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 :
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;class Solution {
public:int mySqrt(int x) {int l = 1, r = x,mid,x_div_mid;while (l <= r){mid = l + (r - l) / 2;x_div_mid = x / mid;if (x_div_mid == mid) { return mid; }if (mid < x_div_mid) { l = mid + 1; }else {r = mid - 1;}}return r;}
};int main() {cout << "请输入x: ";int x;cin >> x;Solution solution;int result = solution.mySqrt(x);cout << result;return 0;
}

这一题思想也是双指针。
要特别注意边界取值的情况，为了防止溢出，mid=L+(R-L)/2。

34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 :
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

代码与书中的方法一样，就不展示了。
书中实现了C++中的lower_bound和upper_bound函数，使用了左闭右开的写法。
易错点：
数组越界，原来我的代码是 while (n2 >-1 || n1>-1)，想着这样就不需要多最后复制剩余值的一步，但是报了越界错误，经常因为不能正确确定界值，造成数组越界，需要注意。