最基本的算法,常用于比较目标值和数组中间元素。时间复杂度为O(logN)。
来自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,这能体现中间值的过程,也能防止溢出问题。
来自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,有空可以学习一下这题的数学思想,牛顿迭代法。