最基本的算法,常用于比较目标值和数组中间元素。时间复杂度为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,有空可以学习一下这题的数学思想,牛顿迭代法。
正文完