二分算法入门(简单题)
习题1
704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入:nums= [-1,0,3,5,9,12],target= 9 输出: 4 解释: 9 出现在nums中并且下标为 4
示例 2:
输入:nums= [-1,0,3,5,9,12],target= 2 输出: -1 解释: 2 不存在nums中因此返回 -1
提示：
- 你可以假设
nums中的所有元素是不重复的。 n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
写法1：
class Solution {public int search(int[] nums,int target) {if(target < nums[0] || target > nums[nums.length - 1]) {return -1;}int left = 0;int right = nums.length - 1;while(left <= right) {int mid = left + (right - left) / 2;if(nums[mid] > target) {right = mid - 1;}else if (nums[mid] < target) {left = mid + 1;}else {return mid;}}return -1;}
}上述写法为第一种写法，我们定义的target所在的区间是一个左闭右闭的区间，也就是[left,right]
区间的定义决定了二分法该如何写，此写法target在[left,right]区间，有以下特点：
1. while (left <= right) 要使用 <= ，因为left == right 是有意义的，故要使用 <=
2. if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle] 一定不是target，那么接下来要查找的做区间结束下标位置就是 middle - 1，left 赋值 middle + 1 同理。
写法2：
class Solution {public int search(int[] nums , int target) {if(target < nums[0] || target > nums[nums.length - 1]) {return -1;}int left = 0;int right = nums.length;while(left < right) {int mid = left + (right - left) / 2;if(nums[mid] < target) {left = mid + 1;}else if(nums[mid] > target) {right = mid;}else {return mid;}}return -1;}
}该写法则是将target定义在一个左闭右开的区间中，也就是[left,right)，此时二分法的边界处理就截然不同
1. while(left < right),这里使用 < ,因为left == right 在区间 [left,right) 是没有意义的.
2. if(nums[mid] > target) right 更新为mid,因为当前nums[mid] 不等于target,去做区间继续寻找,而寻找区间是左闭右开区间,所以right 更新为 mid,而左边界是闭区间,则if(nums[mid] < target) 中,left 更新为 mid + 1.
以下题目均由二分法第一种写法实现
习题2
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums为 无重复元素 的 升序 排列数组-104 <= target <= 104
这道题目其实就是在二分算法的壳子上面做了些许点缀,根本上还是二分算法的应用,但是多了一些特殊情况的判断,题解如下:
class Solution {public int searchInsert(int[] nums, int target) {int n = nums.length;if(target < nums[0]) {return 0;}else if(target > nums[n - 1]){return n;}int left = 0;int right = n - 1;while(left <= right) {int mid = left + (right - left) / 2;if(nums[mid] > target) {right = mid - 1;if(nums[right] < target) {return mid;}}else if(nums[mid] < target) {left = mid + 1;if(nums[left] > target) {return mid + 1;}}else {return mid;}}return -1;}
}从代码实现上不难看出,这其实就是一个二分算法,只不过在特殊情况下做了一些特殊处理,我这里将特殊情况所产生的结果一一进行了返回(有点笨的方法),在处于"左侧"情况与"右侧"情况中无法查询到的数据位置重新进行了判断.
习题3
69. x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
class Solution {public int mySqrt(int x) {int left = 0;int right = x;while(left <= right) {int mid = left + (right - left) / 2;if((long)mid * mid < x) {left = mid + 1;if(left * left > x) {return mid;}}else if((long)mid * mid > x) {right = mid - 1;if((long)right * right < x) {return right;}}else {return mid;}}return -1;}
}这道题目相对上面那道题目又多了一些变化.除了如习题2一般要对特殊条件再判断外,还需要考虑if((long)mid * mid < x) if中条件的变化,我们需要按照题目所给的比较依据来判断if中的条件.