题目704 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4
输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1
class Solution { public int search(int[] nums, int target) { int n = nums.length; int l = 0, r = n; while (l + 1 < r) { int mid = (l + r) >> 1; if (nums[mid] > target) { r = mid; } else { l = mid; } } if (nums[l] == target) return l; return -1; } }题目35 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
输入: [1,3,5,6], 5 输出: 2
输入: [1,3,5,6], 2 输出: 1
输入: [1,3,5,6], 7 输出: 4
输入: [1,3,5,6], 0 输出: 0
class Solution { public int searchInsert(int[] nums, int target) { int n = nums.length; int l = 0, r = n; while (l + 1 < r) { int mid = (l + r) >> 1; if (nums[mid] > target) { r = mid; } else { l = mid; } } if (nums[l] == target) { return l; } else { if (nums[l] < target) { return l + 1; } else { return l; } } } }题目69 实现 int sqrt(int x) 函数。 计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
输入: 4 输出: 2
输入: 1 输出: 1
输入: 8 输出: 2 说明: 8 的平方根是 2.82842…, 由于返回类型是整数,小数部分将被舍去。
class Solution { public int mySqrt(int x) { long l = 0, r = (long)x + 1; while (l + 1 < r) { int mid = (int) ((l + r) / 2); if (check(mid, x)) { // mid*mid > x r = mid; } else { l = mid; } } return (int)l; } public boolean check(int mid, int t) { long res = (long)mid * mid; if (res > t) { return true; } else { return false; } } }