C++算法:二分查找旋转数组

简介: C++算法:二分查找旋转数组

说明

由于题目相对简单,所以代码直接在课程视频中。以后一定注意,保留源码。

题目

已知整数数组nums,先按升序排序后,再旋转。旋转k位后,元素分别为nums[k],nums[k+1]...nums[0]...nums[k-1]。请查找target 是否存在,如果存在返回所在索引;否则返回-1。假定nums没有重复的元素。

假定排序后的数组为{1,2,3,4,5}。

旋转0位:不变。

旋转1位:{2,3,4,5,1}

旋转2位:{3,4,5,1,2}

旋转3位:{4,5,1,2,3}

旋转4位:{5,1,2,3,4}

解题思路

观察后,可以得到如下结论:

旋转数组,可以拆分成左右两个升序数组,且左数组的任意元素都大于右数组的任意元素。

分两步:

  • 找到数组的分界线RBegin,[0,RBegin)是左数组,[RBegin,n)是右数组。特殊情况:只有一个升序数组,则RBegin为0,左数组为空。
  • 如果是小于等于nums.back(),在右边找;否则在左边找。升序寻找元素之前已经讲过了,就不累赘了。
  • 寻找RBegin

nums[mid] < nums.back()

扔掉右边,不扔mid

nums[mid] == nums.back()

扔掉右边,不扔mid

nums[mid] > nums.back()

扔掉左边,扔掉mid

故用左开右闭空间。

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int rBegin = FindRBegin(nums);
        if (target <= nums.back())
        {
            return Find(nums, rBegin, nums.size(), target);
        }
        return Find(nums, 0, rBegin, target);
    }
    int FindRBegin(const vector<int>& nums)
    {
        int left = -1, r = nums.size()-1;//左开右闭
        while (r - left > 1)
        {
            const int mid = left + (r - left) / 2;
            if (nums[mid] <= nums.back())
            {
                r = mid;
            }
            else
            {
                left = mid;
            }
        }
        return r;
    }
    int Find(const vector<int>& nums, int left, int r, int target)
    {
        while (r - left > 1)
        {
            const auto mid = left + (r - left) / 2;
            if (nums[mid] <= target)
            {
                left = mid;
            }
            else
            {
                r = mid;
            }
        }
        return (target == nums[left]) ? left : -1;
    }
};
int main()
{
    vector<int> vNums = {1,2,3,4,6};
    auto res = Solution().search(vNums, 4);
    std::cout << "index:" <<  res;
    if (-1 != res)
    {
        std::cout << " value:" << vNums[res];
    }
}

注意

开发及测试操作系统:Windows10(安装的时候没注意,安装成了英文版)

开发及测试环境:Microsoft Visual Studio 2022  

如果还不明白,请看我的视频;如果看完视频,还是不明白,请下载源码后,直接修改。

其它

视频课程

如果你觉得复杂,想从简单的算法开始,可以学习我的视频课程。

https://edu.csdn.net/course/detail/38771

我的其它课程

https://edu.csdn.net/lecturer/6176

测试环境

win7 VS2019 C++17 或Win10 VS2022 Ck++17

相关下载

算法精讲《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

目录
打赏
0
0
0
0
36
分享
相关文章
|
1月前
|
【C++数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
二分查找的基本思想是:每次比较中间元素与目标元素的大小,如果中间元素等于目标元素,则查找成功;顺序表是线性表的一种存储方式,它用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑上相邻的元素在物理存储位置上也相邻。第1次比较:查找范围R[0...10],比较元素R[5]:25。第1次比较:查找范围R[0...10],比较元素R[5]:25。第2次比较:查找范围R[0..4],比较元素R[2]:10。第3次比较:查找范围R[3...4],比较元素R[3]:15。,其中是顺序表中元素的个数。
145 68
【C++数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
|
3天前
|
算法系列之搜素算法-二分查找
二分查找是一种在`有序`数组中查找特定元素的算法。它的基本思想是通过将数组分成两半,逐步缩小查找范围,直到找到目标元素或确定目标元素不存在。
22 9
算法系列之搜素算法-二分查找
|
11天前
|
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
37 15
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
39 12
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
11 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
70 23
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
61 19
马特赛特旋转算法:Python的随机模块背后的力量
马特赛特旋转算法是Python `random`模块的核心,由松本真和西村拓士于1997年提出。它基于线性反馈移位寄存器,具有超长周期和高维均匀性,适用于模拟、密码学等领域。Python中通过设置种子值初始化状态数组,经状态更新和输出提取生成随机数,代码简单高效。
144 63
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
47 5
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
54 2
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等