二分算法
二分算法模板, 二分搜索即搜索一个数，如果存在，返回其索引，否则返回-1。
int binarySearch(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 注意 while(left <= right) { // 注意 int mid = (right + left) / 2; if(nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; // 注意 else if (nums[mid] > target) right = mid - 1; // 注意 } return -1; }
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
思路
一个数 x 的开方 sqrt 一定在 0 ~ x 之间，并且满足 sqrt == x / sqrt。可以利用二分查找在 0 ~ x 之间查找 sqrt。
代码实现：
public class LeetCode69 { // 二分算法 int mySqrt(int x) { int l = 1; int h = x; while (l <= h) { int mid = l + (h - l) / 2; int sqrt = x / mid; if (sqrt == mid) { return mid; } else if (sqrt < mid) { h = mid - 1; } else { l = mid + 1; } } return h; } public static void main(String[] args) { System.out.println(new LeetCode69().mySqrt(8)); } }
