【leetcode】二分查找专题

文章目录

• 1.基本的二分查找
• 2.使用二分 查找左右端点
• • 2.1 左右端点
  • 2.2 二分模板
• 3.搜索插入位置
• 4.x的平方根
• 5.山脉数组的顶峰
• 6.寻找峰值
• 7.寻找旋转排序数组中的最小值

对于二分查找，相信大家都再熟悉不过了。一旦数据是有序的，我们大概率会想到二分，但是有时候数据不是有序时，也可以使用二分。下面我们就来写几道关于二分的题目。

1.基本的二分查找

题目链接

二分的精髓就在于它一次就可以决定一半数据的归属，该题就是一个最简单的二分题。

由于left和right相遇时可能就是target，所以循环的条件应该是left <= right。

当left与right错开时，就说明没有target这个元素，返回-1。

如果数据太多，left和right较大时，我们计算mid时，left + right可能会溢出；
所以我们可以这样 mid = left + (right - left) / 2 ;

 int search(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 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; }

2.使用二分 查找左右端点

2.1 左右端点

题目链接

对于该题目，就是在朴素二分的基础上，让你在区间中选择两个位置，该位置标记了target元素的开始与结束。

但是我们这一题需要在朴素二分的基础上进行变化。

 vector<int> searchRange(vector<int>& nums, int target) { int left = 0; int right = nums.size()-1; if(nums.size() == 0) return {-1,-1}; int begin = -1; int end = -1; while(left < right) { int mid = left + (right - left) / 2; //小于target，去掉[left,mid]区间 if(nums[mid] < target) left = mid + 1; //大于等于target,去掉(mid,right] else right = mid; } if(nums[left] != target) return {-1,-1}; begin = left; left = 0; right = nums.size() - 1; while(left < right) { int mid = left + (right - left + 1) / 2; //小于等于target，去掉[left,mid)区间 if(nums[mid] <= target) left = mid; //大于target,去掉[mid,right]区间 else right = mid - 1; }  if(nums[left] != target) return {-1,-1}; end = left; return {begin,end}; }

2.2 二分模板

求左端点

 while (left < right) { int mid = left + (right - left) / 2; //小于target，去掉[left,mid]区间 if (...) left = mid + 1; //大于等于target,去掉(mid,right] else right = mid; }

求右端点

 while (left < right) { int mid = left + (right - left + 1) / 2; //小于等于target，去掉[left,mid)区间 if () left = mid; //大于target,去掉[mid,right]区间 else right = mid - 1; }

3.搜索插入位置

由于该题目也具有二段性，因此也使用二分。、

• 当left与right相遇时
  • 如果 nums[left] < target，则表明数组中没有target元素，则target元素应插入到left后面
  • 如果 nums[left] > target，则表明数组中没有target元素，left位置就是target要插入的位置
  • 如果 nums[left] == target，则表明数组中有target元素，left位置就是target的下标

 int searchInsert(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 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; else return left; }

4.x的平方根

题目链接

解法一：暴力查找

使用 i 依次遍历1-x的数，直到 i*i >= x时，就可以出现结果。为了防止溢出，应使用long long

 int mySqrt(int x) { for(long long i=1; i<=x; i++) { if(i* i == x) return i; else if(i *i > x) return i-1; } return 0; }

解法二：二分查找

对于1-x之间的数，它平方的结果具有二段性，要么> x，要么 <= x，因此可以使用二分优化暴力解法。

 int mySqrt(int x) { if(x == 0) return 0; int left = 1; int right = x; while(left < right) { long long mid = left + (right - left + 1) / 2; if(mid * mid <= x) left = mid; else right = mid - 1; } return left; }

5.山脉数组的顶峰

题目链接

根据题目可知，山脉递增以后再递减，那么一定会存在相邻的两个数前者大于后者的情况，此时前者就是峰顶。

解法一：暴力求解

从i = 1下标依次遍历数组，如果nums[i-1] > nums[i]，此时i-1位置就是峰顶。

解法二：二分求解

• 如果nums[i] > nums[i-1]，那么nums[i]之前一定是递增的，峰值还再后面，因此可以排除 i 之前的区间 left = mid;
• 如果nums[i] < nums[i-1]，那么i及后面的都不可能是峰值，right = mid - 1;
• 未避免死循环和mid-1越界，求mid时应选择后面的一个

 int peakIndexInMountainArray(vector<int>& arr) { int left = 0; int right = arr.size()-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; }

6.寻找峰值

任取⼀个点 i ，与前⼀个点 i - 1，会有如下两种情况：

• arr[i] > arr[i - 1] ：此时「右侧区域」⼀定会存在山峰（因为最右侧是负⽆穷），那么我们可以去右侧去寻找结果；
• arr[i] < arr[i - 1] ：此时「左侧区域」⼀定会存在山峰（因为最左侧是负⽆穷），那么我们可以去左侧去寻找结果。
• 注意边界情况

 int findPeakElement(vector<int>& nums) { int left = 0; int right= nums.size()-1; while(left < right) { //防止下标越界和死循环，mid总是取后一个 int mid = left + (right - left + 1) / 2; if(nums[mid] > nums[mid-1])//去右边区域找 left = mid; else right = mid - 1; } return left; }

7.寻找旋转排序数组中的最小值

题目链接

由于数组原本是一个有序的数组，那么旋转后数组就会变成含有两段有序元素的数组。

对于任意一个点 i 而言，我们就是要找C的位置

• 如果nums[i]落在AB区间中，也就是nums[i] > nums[D]，此时应该去 [i+1，D]区间中找，即left = mid + 1
• 如果nums[i]落在CD区间中，也就是nums[i] < nums[D]，此时应该去[C，i]区间中找，即right = mid;
• 当区间长度变为1时，就是结果

 int findMin(vector<int>& nums) { int n = nums.size()-1; int left = 0; int right = n; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] > nums[n]) left = mid + 1; else right = mid; } return nums[left]; }