今日主题：二分查找。
35. 搜索插入位置
问题描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
解题思路
两端都闭的二分查找。
代码实现
class Solution {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
int left = 0, right = len -1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
//右侧
left = mid + 1;
}else {
//左侧
right = mid - 1;
}
}
return left;
}
}
69. x 的平方根
问题描述
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
解题思路
由于 x 平方根的整数部分是满足 k^2 ≤x 的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。
- 注意处理大整形求平方时的整形溢出问题
代码实现
class Solution {
public int mySqrt(int x) {
if(x < 2){
//0的平方根是0
return x;
}
long left = 1, right = x;
while(left <= right){
long mid = left + (right - left) / 2;
long sqrt = mid * mid;
if(sqrt == x){
return (int) mid;
}else if(sqrt < x){
left = mid + 1;
}else {
right = mid - 1;
}
}
return (int) left - 1 ;
}
}
