文章目录
前言
最近也是有在刷一些算法题，进度是跟着这个链接的。算法。现在把做过的题记录下来，写写思路，后面还可以经常翻翻。本文就介绍下二分以及一些LeedCode上面的题目。当然这些二分都是基于看了题解之后我的理解，如果有错误欢迎指出。
1. 二分查找
关于二分查找，其实就是折半查找。这里用一个场景说明二分查找：给一个升序的数组，要我们寻找到其中的一个值。常规的思路就是遍历一遍，时间复杂度当然是O(n)了。而二分查找就是从中间开始查找，先比较中间的和 target 目标值，如果中间值比较大，证明 target 在左半部分，然后再次以左半部分来进行二分搜索。这样每一次都可以减少一半的工作量，时间复杂度是 O(logn) 级别的。下面是具体的案例：
2. 二分的其中三种写法
1. 将区间分为 [L, mid] 和 [mid + 1, R]
/*
1、二分模板第一种
将区间[L, R]划分成[L, mid]和[mid + 1, R]
*/
public int binaryOne(int[] arr, int L, int R, int target) {
while (L < R) {
//防止下标越界：（a + b）/2 可能发生越界问题
int mid = L + ((R - L) >> 1);
if (arr[mid] > target) {
//r = middle
R = mid;
} else if (arr[mid] < target) {
//l = middle + 1
L = mid + 1;
} else {
return mid;
}
}
return -1;
}
2. 将区间分为 [L, mid-1] 和 [mid, R]
public int binaryTwo(int[] arr, int L, int R, int target) {
while (L < R) {
int middle = L + (R - L + 1) / 2;
if (arr[middle] > target) {
R = middle-1;
} else if (arr[middle] < target) {
L = middle;
} else {
return middle;
}
}
return -1;
}
3. 将区间分为 [L, mid-1] 和 [mid+1, R]
这段代码就直接复制别人的了。
public int search(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid;
}
return -1;
}
4. 对比这三种写法
只是因为区间不同，导致求中点的方式不同。那么对于第二种写法，采用的是 L + (R - L + 1) / 2 向上取整的方式，比如 L = 0, R = 5 的时候求出来的就是下标 3 的位置，如果是第一种方法，求出来的是 2，那么为什么会有这种区别呢？这样写其实就是为了防止死循环。我们假设现在有一个数组是[1, 2 ,3 ,4 ,5 ,7 ,8, 9], 要求的target = 6, 那么当我们使用方式二进行二分的时候，如果还是 middle = L + (R - L) /2, 这时候就会有问题。
第一次二分：L = 0, R = 7, mid = 3, 发现 4 < 6,
第二次二分：L = 3, R = 7, mid = 5, 发现7 > 6
第三次二分：L = 3, R = 4, mid = 3, 发现4 < 6
第四次二分：L = 3, R = 4, mid = 3 …
一直死循环下去了
那么为什么会出现这种问题呢，假设 R = L + 1, 而 (L, R)之间区间是没有这个 target 的，也就是说 arr[L] < target, arr[R] > target，此时 mid 求出来(L + R - 1) / 2 = (L + L + 1 - 1) / 2 = L，满足了 arr[middle] < target 的条件，这时候 L = mid = L ，也就是说 L 是不变的。所以这里我们采用了 middle = (L + R + 1) / 2 这种方法来求。因为 L = middle, 所以当 middle 向上取整的时候 middle = R, 这时候 L = R 就可以退出循环了。
至于为什么这种求中点的方法也可以，我的理解就是中点位置可以在左边也可以在右边，换句话说，能刚好求出来一个整数是最好的，比如 L = 0, R = 4 的情况。而如果不能刚好求出一个整数，那么我们就要考虑自己的划分区间的方式来决定数值是向上取整还是向下取整。而第三种写法就没什么可以说的了，标准的一个二分查询，也是常用的，只是划分区间不同。
最后想说下其实用的最多的还是第一种和第三种
3.LeedCode
1. LeedCode 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
典型的二分查找
//方法1
public int search(int[] nums, int target) {
int R = nums.length-1;
int L = 0;
while (L < R) {
int middle = L + (R - L + 1) / 2;
if (nums[middle] > target) {
R = middle-1;
} else if (nums[middle] < target) {
L = middle;
} else {
return middle;
}
}
//注意这里由于没有提供 L = R 时候的比较，最后还得判断一次，因为当 L = R的时候退出循环了
return nums[L] == target ? L : -1;
}
//方法2
public int search(int[] nums, int target) {
int R = nums.length-1;
int L = 0;
while (L < R) {
//防止下标越界：（a + b）/2 可能发生越界问题
int mid = L + ((R - L) >> 1);
if (nums[mid] > target) {
//r = middle
R = mid;
} else if (nums[mid] < target) {
//l = middle + 1
L = mid + 1;
} else {
return mid;
}
}
return nums[L] == target ? L : -1;
}
2. LeedCode 35
LeedCode35
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:
输入: nums = [1], target = 0
输出: 0
而是一道经典二分了，我们使用第三种解法,这道题也是用这种方法比较方便，有兴趣可以试下其他两种方法：
public int searchInsert(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;
while(start <= end){
int mid = start + (end - start)/2;
if(nums[mid] > target){
end = mid-1;
}else if(nums[mid] < target){
start = mid+1;
}else{
return mid;
}
}
return start;
}
3. LeedCode 34
LeedCode34
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
使用两次二分法，一次查找左边的，一次查找右边的。里面有些小细节要注意的下面都注释了，当然这道题调用两次方法3也是可以的，官方的题解也是用的方法3。
public int[] searchRange(int[] nums, int target) {
//如果中间位置的值等于target, 就返回两边的值
if (nums.length == 0) {
return new int[]{-1, -1};
}
int L = 0;
int R = nums.length - 1;
int flag = 0;
//[l, mid], [mid+1, r]
while (L < R) {
int middle = L + (R - L) / 2;
if (nums[middle] >= target) {
R = middle;
} else if (nums[middle] < target) {
L = middle + 1;
}
}
if(nums[L] != target){
return new int[]{-1, -1};
}
int resL = L;
//上面的左边界是L
//再找到右边的边界, 找右边界使用方法2, 要向上取整
//如果R=l+1, 使用middle=(R+L)/2得到的是L, 得不到右边界R
L = 0;
R = nums.length - 1;
//分成[l, mid-1], [mid, r]
while (L < R) {
int middle = L + (R - L + 1) / 2;
if (nums[middle] > target) {
R = middle-1;
} else if (nums[middle] <= target) {
L = middle;
}
}
return new int[]{resL, R};
}
此外，LeedCode69， LeedCode367也是二分查找的内容，感兴趣可以自己尝试去做
如有错误，欢迎指出！！！