二分查找
模板一
int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while(left <= right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid - 1; }
}
// End Condition: left > right
return -1;
}
- 初始条件:
left = 0, right = length-1
- 终止:
left > right
- 向左查找:
right = mid-1
- 向右查找:
left = mid+1
例题1
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 :
输入: 4 输入: 8
输出: 2 输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数,小数部分将被舍去。
题解:
public int mySqrt(int x) {
int left = 0;
int right = x;
int ans = -1;
while (left <= right) {
int middle = (left + right) / 2;
if ((long) middle * middle <= x) {
ans = middle;
left = middle + 1;
} else {
right = middle - 1;
}
}
return ans;
}