二分查找简介
1.特点
最简单最恶心，细节最多，最容易写出死循环的算法
2.学习中的侧重点
1）算法原理
数组有序的情况
2） 模板
不要死记硬背 ->理解之后再记忆
1.朴素的二分模板
2.查找左边界的二分模板
3.查找右边界的二分模板//后面两个是万能模板，细节很多
1.二分查找
1）题目描述
2）算法原理
二分查找
根据规律能把数组分为两部分，可以用二分查找（选择中间这个点的时间复杂度是最小的）
class Solution {public int search(int[] nums, int target) {int left=0,right=nums.length-1;while(left<=right){int mid=(left+right)/2;if(nums[mid]==target){return mid;}else if(nums[mid]>target){right=mid-1;}else{left=mid+1;}}return -1;}
}我们在计算mid的时候要考虑数字的溢出
int mid=left+(right-left)/2;
class Solution {public int search(int[] nums, int target) {int left=0,right=nums.length-1;while(left<=right){// int mid=(left+right)/2;int mid=left+(right-left)/2;//防止溢出if(nums[mid]==target){return mid;}else if(nums[mid]>target){right=mid-1;}else{left=mid+1;}}return -1;}
}朴素版本的时候 :
mid=left+(right-left+1)/2;==mid=left+(right-left)/2;
2.在排序数组中查找元素的第一个和最后一个位置
1）题目描述
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。示例 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]
2）算法原理
仍然是用朴素二分
class Solution {public int[] searchRange(int[] nums, int target) {//首先进行特殊情况的处理if(nums.length==0){return new int[]{-1,-1};}if(nums.length==1){return nums[0]==target?new int[]{0,0}:new int[]{-1,-1};}int l=0,r=nums.length-1;while(l<=r){int mid=(l+r)/2;if(nums[mid]==target){l=r=mid;//找到左标记while(l>=1&&nums[l-1]==target){l--;}//找到右标记while(r<nums.length-1&&nums[r+1]==target){r++;}return new int[]{l,r};}if(nums[mid]>target){r=mid-1;}else{l=mid+1;}}return new int[]{-1,-1};}
}但是如果数组全是3的话，我们的时间复杂度又会降成O(N)
class Solution {public int[] searchRange(int[] nums, int target) {int[] ret=new int[2];ret[0]=ret[1]=-1;//1.处理边界条件int n=nums.length;if(n==0){return ret;}//2.二分左端点int left=0,right=n-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}else{right=mid;}}//判断是否有结果if(nums[left]!=target){return ret;}else{ret[0]=left;}//2.二分右端点left=0;right=n-1;while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]>target){right=mid-1;}else{left=mid;}}//判断是否有结果if(nums[right]!=target){return ret;}else{ret[1]=right;}return ret;}
}
3.x的平方根
69. x 的平方根 - 力扣（LeetCode）
1）题目描述
给你一个非负整数
x，计算并返回x的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如
pow(x, 0.5)或者x ** 0.5。示例 1：
输入：x = 4 输出：2示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
2）算法原理
class Solution {public int mySqrt(int x) {if(x<1){return 0;}long left=0,right=x;while(left<right){long mid=left+(right-left+1)/2;//防止溢出if(mid*mid>x){right=mid-1;}else{left=mid;}}return (int)left;}
}4.搜索插入位置
1）题目描述
35. 搜索插入位置 - 力扣（LeetCode）
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
O(log n)的算法。
2）算法原理
class Solution {public int searchInsert(int[] nums, int target) {//首先进行特殊情况的处理if(nums.length==0){return 0;}int left=0,right=nums.length-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}else{right=mid;}}//二分法只能处理在数组中间的情况,我们是在数组中找结果//所以需要特判if(nums[left]<target){return left+1;}return left;}
}left和right相遇了，想写谁写谁
5.山脉数组的峰顶索引
852. 山脉数组的峰顶索引 - 力扣（LeetCode）
1）题目描述
给定一个长度为
n的整数 山脉 数组arr，其中的值递增到一个 峰值元素 然后递减。返回峰值元素的下标。
你必须设计并实现时间复杂度为
O(log(n))的解决方案。示例 1：
输入：arr = [0,1,0] 输出：1示例 2：
输入：arr = [0,2,1,0] 输出：1示例 3：
输入：arr = [0,10,5,2] 输出：1
2）算法原理
class Solution {public int peakIndexInMountainArray(int[] arr) {int left=0,right=arr.length;while(left<right){int mid=left+(right-left+1)/2;if(arr[mid]>arr[mid-1]){//此时说明在左半边left=mid;}else if(arr[mid]<arr[mid-1]){//说明在右侧right=mid-1;}}return left;}
}6.寻找峰值
寻找峰值
1）题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组
nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设
nums[-1] = nums[n] = -∞。你必须实现时间复杂度为
O(log n)的算法来解决此问题。
2）算法原理
class Solution {public int findPeakElement(int[] nums) {int left=0,right=nums.length-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<nums[mid+1]){left=mid+1;}else if(nums[mid]>nums[mid+1]){right=mid;}}return left;}
}7.寻找排序数组的最小值
1）题目描述
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
已知一个长度为
n的数组，预先按照升序排列，经由1到n次 旋转 后，得到输入数组。例如，原数组nums = [0,1,2,4,5,6,7]在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2]- 若旋转
7次，则可以得到[0,1,2,4,5,6,7]注意，数组
[a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值 互不相同 的数组
nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为
O(log n)的算法解决此问题。示例 1：
输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。示例 2：
输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。示例 3：
输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
2）算法原理
class Solution {public int findMin(int[] nums) {int n = nums.length - 1;int left = 0, right = n;while (left < right) {int mid=left+(right-left)/2;if(nums[mid]>nums[n]){left=mid+1;}else if(nums[mid]<=nums[n]){right=mid;}}return nums[left];}
}8.0~n-1中缺失的数字
1）题目描述
LCR 173. 点名 - 力扣（LeetCode）
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组
records。假定仅有一位同学缺席，请返回他的学号。示例 1:
输入: records = [0,1,2,3,5] 输出: 4示例 2:
输入: records = [0, 1, 2, 3, 4, 5, 6, 8] 输出: 7提示：
1 <= records.length <= 10000
2）算法原理
class Solution {public int takeAttendance(int[] records) {int left=0,right=records.length-1;//1.处理特殊情况if(records[right]==right){return right+1;}while(left<right){int mid=left+(right-left)/2;if(records[mid]==mid){left=mid+1;}else{right=mid;}}return left;}
}