数据结构之二分查找OJ（上）
1.二分查找
2.搜索插入位置
3.在排序数组中搜索第一个和最后一个位置
4.搜索旋转数组的最小值
5.搜索旋转数组II
6.搜索旋转数组（面试题）
7.寻找旋转数组中的最小值
8.搜索旋转数组中的最小值II
9.找到数组中局部最小的数
1.二分查找
对应letecode链接：
704. 二分查找 - 力扣（LeetCode） (leetcode-cn.com)
题目描述：
解题思路：
首先根据数组的起始位置的下标和末尾位置的下标计算出中间位置的下标，在取出中间位置的值和要查找的值进行比较。
在本图中:
由于要查找的元素20，大于中间元素12，再次定位右到数组半部分的中间元素：
刚好查找到了20这个元素。
如果数组的长度为N，那么时间复杂度为O（log N)空间复杂度为O（1）。
对应代码：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0;
int right=nums.size()-1;
int ans=-1;
while(left<=right){
int mid=(left+right)>>1;//求中点
if(nums[mid]==target){//找到了
ans=mid;
break;
}
else if(nums[mid]<target){
left=mid+1;
}
else{
right=mid-1;
}
}
return ans;
}
};2.搜索插入位置
35. 搜索插入位置 - 力扣（LeetCode） (leetcode-cn.com)
题目描述：
解题思路：
本题和上题思路十分类似只需要找到最左边大于等于target的元素即可，算法流程如下：
1.求出中点和target比较
2.如果终点位置的值大于等于target则砍调右边的
3.终点位置的值小于target则砍调左边的。
4.如果target比数组中所有元素都打说明是在数组的末尾插入的。
对应代码：
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int index=-1;//记录答案下标
int left=0;
int right=nums.size()-1;
while(left<=right){
int mid=(left+right)>>1;
if(nums[mid]>=target){//大于等于往左边走找到最左边大于等于target的位置
index=mid;
right=mid-1;
}
else{
left=mid+1;
}
}
return index==-1?nums.size():index;//如果上面没有更新过答案说明插入位置在数组的末尾
}
};3.在排序数组中搜索第一个和最后一个位置
对应letecode链接：
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） (leetcode-cn.com)
题目描述：
解题思路：
1.利用二分查找找到比target小的最右边的位置
2.将返回的位置+1看是否已经越界或者值不等于target
3.查找比target+1小的最右边的位置即target。
对应代码：
class Solution {
public:
int FindIndex(vector<int>&nums,int target){
int left=0;
int right=nums.size()-1;
int ans=-1;//记录答案找比target小的最右的位置
while(left<=right){
int mid=(left+right)>>1;
if(nums[mid]<target){//只要比target要小就记录答案
left=mid+1;
ans=mid;
}
else{
right=mid-1;
}
}
return ans;
}
vector<int> searchRange(vector<int>& nums, int target) {
int L=FindIndex(nums,target)+1;//在比target小的最右边的位置在加个1
if(L==nums.size()||nums[L]!=target){//如果已经越界了或者这个位置的值不是target
return {-1,-1};
}
return {L,FindIndex(nums,target+1)};//找到比target+1小的最右边的数即target
}
};4.搜索旋转数组的最小值
对应letecode链接：
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode） (leetcode-cn.com)
题目描述：
解题思路：
解题思路：
1.定义一个变量记录答案
2.取中点和左边的值进行比较如果左边的值小于等于右边的值说明左边有序，在判断target是否在这个区间里面，如果在right=mid-1,否则left=mid+1.
3.如果左边无序则说明右边有序，同样的判断是否在这个区间里面如果在的话left=mid+1,否则right=mid-1.
以下面为例：
根据上面的图，我们可以直观看出一个规律，如何判断是不是被旋转打乱了？正常升序的前提条件是 first element <= last element ，而乱序的条件则是：first element > last element
然后再继续挖掘一下乱序数组的规律，那就是乱中有序，如何理解呢 ？
对应代码：
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty())//如果为空
return -1;
int left=0;
int right=nums.size()-1;
int ans=INT_MAX;
while(left<=right){
int mid=(left+right)/2;
if(nums[mid]==target)
ans=mid;
if(nums[mid]>=nums[left]){//如果左边有序
if(target>=nums[left]&&target<=nums[mid]){//如果在这个区间里面
right=mid-1;
}
else{
left=mid+1;
}
}
else{//右边有序
if(target>=nums[mid]&&target<=nums[right]){
left=mid+1;
}
else{
right=mid-1;
}
}
}
return ans==INT_MAX?-1:ans;
}
};5.搜索旋转数组II
对应letecode链接：
81. 搜索旋转排序数组 II - 力扣（LeetCode） (leetcode-cn.com)
题目描述
解题思路：
本题于上题不一样的是可能出现重复的元素，当左边和右边的值相等时我们就无法判断[left,,mid]和[mid,right]这两个区间那个有序的。所以我们需要将右边，值和左边的值相等的部分删掉在按照上题的思路即可
对应代码：
class Solution {
public:
bool search(vector<int>& arr, int target) {
int l = 0, r = arr.size() - 1;
int ans = INT_MAX;
while(l < r && arr[l] == arr[r]){
r--;
}
while(l <= r){
int mid = (l+r)/2;
if(arr[mid] == target){//相等找到了
ans = mid;
break;
}
if(arr[l] <= arr[mid]){//左边有序
if(arr[l] <= target && target <= arr[mid]){
r = mid - 1;
}else {
l = mid + 1;
}
}else {//右边有序
if(arr[mid] <= target && target <= arr[r]){
l = mid + 1;
}else {
r = mid - 1;
}
}
}
return ans == INT_MAX ? false : true;
}
};6.搜索旋转数组（面试题）
对应letecode链接：
面试题 10.03. 搜索旋转数组 - 力扣（LeetCode） (leetcode-cn.com)
题目描述：
解题思路：和上题基本一样只不过要更新一下答案而已。
对应代码：
class Solution {
public:
int search(vector<int>& arr, int target) {
int l = 0, r = arr.size() - 1;
while(l < r && arr[l] == arr[r]){//删除右边和左边值相等都部分
r--;
}
int ans = INT_MAX;
while(l <= r){
int mid = ((r - l) >> 1) + l;
if(arr[mid] == target){//相等
ans = min(ans, mid);//更新下标
}
if(arr[l] <= arr[mid]){//[l,mid]有序
if(arr[l] <= target && target <= arr[mid]){
r = mid - 1;
}else {
l = mid + 1;
}
}else {//[mid,r]有序
if(arr[mid] <= target && target <= arr[r]){
l = mid + 1;
}else {
r = mid - 1;
}
}
}
return ans == INT_MAX ? -1 : ans;
}
};7.寻找旋转数组中的最小值
对应letecode链接：
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode） (leetcode-cn.com)
题目描述：
解题思路：
我们要找到数组中的最小值我们先利用二分找到中间元素的值和最后一个值进行比较，如果中点位置的值比最后一个元素的值要小说明在第二段中让right=mid否则left=mid+1.知道left=mid就找到了最小的元素。
对应代码：
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.size()==1)//只有一个元素
return nums[0];
if(nums[0]<nums.back())//本来就是有序的
return nums[0];
int left=0;
int right=nums.size()-1;
while(left<right){
int mid=(left+right)>>1;//取中点
if(nums[mid]<nums.back()){//说明在第二段
right=mid;
}
else{
left=mid+1;
}
}
return nums[left];
}
};8.搜索旋转数组中的最小值II
对应letecode链接：
154. 寻找旋转排序数组中的最小值 II - 力扣（LeetCode） (leetcode-cn.com)
题目描述
解题思路：
本题思路和上题基本一样只不过同样会有左边和右边元素相等同样会无法判断是否在那一边所以我们需要将右边，值和左边值相等的部分给删掉之后和上题就是一样的了。
对于代码：
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.size()==1)
return nums[0];
int left=0;
int right=nums.size()-1;
while(left<right&&nums[left]==nums[right])//将相等的部分去除掉
right--;
if(nums[left]<=nums[right])
return nums[left];
while(left<right){
int mid=(left+right)/2;
if(nums[mid]<nums[0]){//说明在在旋转的拿一部分
right=mid;
}
else{
left=mid+1;
}
}
return nums[left];//返回结果
}
};9.找到数组中局部最小的数
数组中找到一个局部最小的位置_牛客题霸_牛客网 (nowcoder.com)
题目描述：
解题思路：
按照题目的定义进行二分具体请看代码：
#include<iostream>
#include<vector>
using namespace std;
int GetMin(vector<int>&arr){
int n=arr.size();
//边界条件
if(arr.size()==1){
return 0;
}
if(arr[0]<arr[1]){
return 0;
}
if(arr[n-1]<arr[n-2]){
return n-1;
}
int left=0;
int right=n-1;
while(left<right-1){//剩下两个数最后所以是left<righ-1
int mid=(left+right)>>1;
if(arr[mid]<arr[mid-1]&&arr[mid]<arr[mid+1]){//找到了
return mid;
}
else{
if(arr[mid]>arr[mid-1]){
right=mid-1;
}
else{//arr[mid]>arr[mid+1]找到一边
left=mid+1;
}
}
}
return arr[left]<arr[right]?left:right;//比较
}
int main(){
int n;
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<GetMin(arr);
return 0;
}版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/qq_56999918/article/details/123585575
内容来源于网络，如有侵权，请联系作者删除！
