算法(六) 二分查找
最基本的算法，常用于比较目标值和数组中间元素。时间复杂度为O(logN)。
1，例题
1,二分查找
来自LeetCode704
- 最最简单的二分题了，，，，面试热度那么高闹哪样呢，，，，
解法
class Solution {
public int search(int[] nums, int target) {
int middle;
int left = 0;
int right = nums.length - 1;
while(left<=right){
middle = left + (right - left)/2;
if(nums[middle] == target)
return middle;
else if(nums[middle] < target){
left = middle + 1;
}
else
right = middle - 1;
}
return -1;
}
}务必注意二分式子，不可以(left+right)/2。
理解
1，二分式子不可以直接 middle = (left+right）/2，这样遇到nt测试用例，可能加起来会溢出。不过这个式子也并非原始式子。
原始式子应该是middle = left + (left - right)/2，这能体现中间值的过程，也能防止溢出问题。
2,x的平方根
来自LeetCode69
- 计算机的方法很简单
- 数学方法真特么难啊，还好没学数学（牛顿迭代法）
解法
class Solution {
public int mySqrt(int x) {
if(x==0||x==1)
return x;
int l = 0;
int r = x;
int res = -1;;
while(l<=r){
int middle = l + (r - l)/2;
if(x/middle<middle){
r = middle-1;
}
else if(x/middle>middle){
l = middle+1;
if(x/(middle+1)<(middle+1))
return middle;
}
else
return middle;
}
return -1;
}
}务必注意二分式子，不可以(left+right)/2。
理解
1，有空可以学习一下这题的数学思想，牛顿迭代法。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-08-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录