目录:
4.6 题六:点名 (原:剑指Offer:0~n-1 中缺失的数字 )
1、二分查找算法简介
算法,是一种思想,并不是固定的模式,我们可以使用一种算法思想解决多种问题。
二分查找算法,是一个细节最多、最恶心、最容易写出死循环的一个算法,但是当我们熟练掌握后它就可以变成一个最简单的算法,利用它,仅仅使用十几行代码就可以解决掉一个难题,所以在算法学习的路途中,二分查找算法的学习是极为重要且必不可少的。
二分法查找算法的使用条件:数据具有“二段性”。(并非数据有序)
注意:并不是只有数据有序的情况下才可以使用二分查找算法,只要数据具有二段性,即使数据乱序,也可以使用二分查找算法!!!
2、算法原理及时间复杂度分析
这里通过例题为大家讲解算法原理。
2.1 朴素二分算法
使用二分查找算法的关键点是:数据具有“二段性”。
因为数组为升序排列,所以target左边的数据均<target,target右边的数据均>target,故可将数据分为“二段”,具有二段性,可以使用二分查找算法。
定义left和right指针分别指向数组0下标处和nums.length-1处,以及定义他们的中间位置mid,将nums[mid]和target比较,
- nums[mid] < target ---> left = mid+1;
- nums[mid] > target ---> right = mid-1;
- nums[mid] == target ---> 返回结果;
这样一次比较即可过滤掉一半数据,大大提高了查找效率。、
注意:
- 循环条件为:left <= right
- 为防止数据溢出,更新mid的方式为:mid = left + (right - left) / 2;或者mid = left + (right - left + 1) / 2;
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while (left <= right) {
int mid = left+(right-left)/2;
if(nums[mid] < target) {
left = mid+1;
} else if (nums[mid] > target) {
right = mid-1;
}else {
return mid;
}
}
return -1;
}
}
注意:朴素二分算法因为太过简单,所以基本不会考察,重点是下方的边界二分查找算法的思想。
3.2 查找左右边界的二分算法
因为数组为非递减排序,也就是说数据要么相等,要么递增,而我们要找的就是相等数据target的开始和结束位置。
也就是说,我们要找到target的左边界位置和右边界位置,而target的左边的数据小于target,右边的数据大于target,数据同样具有二段性,可以使用二分查找算法。
同样定义left和right指针,定义mid指向他们的中间位置。
3.2.1 查找左边界
- 循环条件为:left < right,left == right时就是最终结果,结束循环
- nums[mid] < target ---> left = mid+1;//mid的位置肯定不为左边界,所以left = mid+1
- num[mid] >= target ---> right = mid;//mid的位置可能就是左边界,所以right=mid
- 更新mid:mid = left + (right - left) / 2;
3.2.2 查找右边界
- 循环条件为:left < right,left == right时就是最终结果,结束循环
- nums[mid] <= target ---> left = mid;//mid的位置可能就是右边界,所以left=mid
- nums[mid] > target ---> right = mid-1;//mid的位置肯定不为右边界,所以right= mid-1
- 更新mid:mid = left + (right - left + 1) / 2;因为更新right或left时,有-1操作,所以这里更新mid要+1(技巧,记忆即可)
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int[] arr = new int[]{-1,-1};
//nums为空数组
if (nums.length == 0) return arr;
//查找左边界
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
}else {
right = mid;
}
}
//数组中不存在target
if (nums[left] != target) return arr;
arr[0] = left;
left = 0;
right = nums.length - 1;
//查找右边界
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] <= target) {
left = mid;
}else {
right = mid - 1;
}
}
arr[1] = left;
return arr;
}
}
注意:
- 朴素二分算法的循环条件是:left <= right;因为要查找的数据可能就在left和right重叠的位置处。
- 边界二分算法的循环条件是:left < right;因为当left == right时,就是最终结果。
- 为避免数据溢出:mid = left + (right - left) / 2 或者 mid = left + (right - left + 1) / 2,朴素算法+1与否都可以,但是在找边界的二分算法中,若更新left或者right时,有-1出现,则更新的mid要+1。
3.3 时间复杂度分析
第一次二分查找剩下n/2个数据,第二次二分查找剩下n/4个数据,第三次二分查找升序n/8个数据,直至最后一次(第x次)二分查找剩下1个数据(此时查找成功),则 == 1,计算得x == logN,因为x就是循环执行的次数,故二分查找算法时间复杂度为:O(logN)
大家可能觉得O(logN)对于O(N)的提升不是很大,其实并不是这样,举个例子:
假设存储了个数据,若用O(N)的算法去查找某一个数据,即遍历所有数据,那么最多需要查找=4,294,967,296次;而使用O(logN)的算法,则最多查找32次就可以查找成功。
综上所述,O(logN)相对于O(N)的提升非常的大,故二分查找算法是一个极为高效的算法,每次都能排除掉一半的数据,从而快速定位到目标位置。
3、二分查找算法模版
对于算法的模版,一定不要死记硬背,要理解后再记忆,这样才可以在不同的题目中灵活使用该算法。
3.1 朴素二分模版
朴素二分模版是最简单的二分模版,因为简单,所以也很少考察。
注意:朴素模版中的循环条件为: left <= right
//朴素二分模版
while (left <= right) {
int mid = left + (right - left) / 2;//避免数据溢出
//int mid = left + (right - left + 1) / 2;在朴素二分中,加不加1均可
if(....) {
left = mid+1;
} else if (....) {
right = mid-1;
}else {
return ....;
}
}
3.2 查找左右边界的二分模版
注意:边界模版中的循环条件为: left < right
4、算法应用【leetcode】
4.1 题一:搜素插入位置
4.1.1 思路分析
分析数据,可以发现target要插入的位置就是第一个比target大的数据的位置,而这个位置左侧的均小于target,右侧的数据均大于target,故具有二段性,可以使用二分查找算法。
而我们的目的就是:找到第一个大于target的数据的位置,返回这个位置的下标即可。
需要注意一个边界情况:当target比所以数据都大时,也就是说target要插入数组的末尾,需要特殊处理。
4.1.2 算法代码
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
}else {
right = mid;
}
}
return target > nums[left] ? left + 1 : left;
}
}
4.2 题二:x的平方根
4.2.1 思路分析
分析数据,因为目标数据的平方是 小于或等于 x的,所以目标数据及其左侧数据(包括目标数据)的平方均小于等于x,右侧数据的平方均大于x。故具有二段性,可使用二分查找算法解决该题。
4.2.2 算法代码
class Solution {
public int mySqrt(int x) {
long left = 0;
long right = x;
while (left < right) {
//mid*mid 可能超出范围,定义为long长整型
long mid = left + (right - left + 1) / 2;
if (mid * mid <= x) {
left = mid;
}else {
right = mid - 1;
}
}
return (int)left;
}
}
4.3 题三:山峰数组的峰顶索引
4.3.1 思路分析
由题意可知,数组一定为山峰,故峰顶左侧的数据一定小于峰顶值,峰顶右侧的数据一定大于峰顶值,故数据具有二段性,可使用二分查找算法。且题目已说明使用O(logN)的算法,故必须使用二分查找算法。
算法思想很简单:
- 若arr[mid] > arr[mid-1],则峰顶一定在mid右侧或峰顶就为mid;//left = mid
- 若arr[mid] < arr[mid-1],则峰顶一定在mid左侧;//right = mid-1
4.3.2 算法代码
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if(arr[mid] > arr[mid - 1]) {
left = mid;
}else {
right = mid - 1;
}
}
return left;
}
}
4.4 题四:寻找峰值
4.4.1 思路分析
该题思路与上一题山峰数组的解题思路是一模一样的,只不过可能存在多个山峰,也就是说数组是完全无序的,所以,二分查找算法的使用并不局限于有序数组,只要数据具有二段性,就可以使用二分查找算法。
- 将中间值arr[mid]与arr[mid-1]比较,若arr[mid] < arr[mid-1],说明在左侧一定有峰值,而右侧是不确定的,可能有也可能没有,这样就可以过滤掉右侧数据,在左侧数据继续寻找山峰;
- 同样,若arr[mid] > arr[mid-1],说明右侧一定有山峰,而左侧不确定,过滤左侧数据,故发现数据具有二段性,能够使用二分查找算法。
- 因为 nums[-1] = nums[n] = -∞,所以即使数组为递增或递减序列时,也能够正确查找到峰值的位置。
4.4.2 算法代码
class Solution {
public int findPeakElement(int[] arr) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if(arr[mid] > arr[mid - 1]) {
left = mid;
}else {
right = mid - 1;
}
}
return left;
}
}
4.5 题五:寻找旋转排序数组中的最小值
4.5.1 思路分析
因为数组原来是升序排列,所以经过旋转,数值大的元素就移动到了数组的前面部分。
所以:
- 未经过旋转的元素必然小于等于数组的最后一个元素。
- 而经过旋转的元素必然大于数组的最后一个元素。
- 故数据具有二段性,可以使用二分查找算法。
因为我们是和数组的最后一个元素比较,所以即使在数组完全旋转的特殊情况下也可以得到正确结果。
而如果是和数组的第一个元素比较的话,在特殊情况时,还需特殊处理,这种解法留给大家,可以锻炼大家的代码能力以及加强对二分查找算法的理解。
4.5.2 算法代码
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= nums[nums.length-1]) {
right = mid;
}else {
left = mid + 1;
}
}
return nums[left];
}
}
4.6 题六:点名 (原:剑指Offer:0~n-1 中缺失的数字 )
4.6.1 思路分析
- 在数组中,缺失的数字前的数据其值与其下标是相对应的。
- 缺失的数字后的数据其值都比其下标大1,故数据具有二段性,可以使用二分查找算法。
- 第一个数值与下标不对应的数据的位置,就是缺失的数据。
特殊情况:缺的是最后一个数据时,数组中的所有数据与其下标均对应,此时需要特殊处理。
4.6.2 算法代码
class Solution {
public int takeAttendance(int[] records) {
int left = 0;
int right = records.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (records[mid] > mid) {
right = mid;
}else {
left = mid + 1;
}
}
return records[left] == left ? left + 1 : left;
}
}
END
标签:二分,right,int,mid,力扣,算法,查找,left From: https://blog.csdn.net/2401_83595513/article/details/141497918