leetcode - [35. 搜索插入位置]

zz/2024/5/21 21:17:31
leetcode - [35. 搜索插入位置]

题目大意

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

解题思路

  • 给出一个已经从小到大排序后的数组,要求在数组中找到插入 target 元素的位置。
  • 这一题是经典的二分搜索的变种题,在有序数组中找到最后一个比 target 小的元素。
#include <stdio.h>
int binary_search(int A[], int n, int key)
{int low = 0;int high = n - 1;while(low <= high){int mid = low + (high - low) / 2;if(A[mid] == key){return mid;}if(key > A[mid]){low = mid + 1;}else{high = mid - 1;}}return low;
}int searchInsert(int A[], int n, int target)
{if(n == 0) return n;return binary_search(A, n, target);
}int main()
{int a[] = {1,3,5,6};printf("%d -> %d\n", 5, searchInsert(a, 4, 5));printf("%d -> %d\n", 2, searchInsert(a, 4, 2));printf("%d -> %d\n", 7, searchInsert(a, 4, 7));printf("%d -> %d\n", 0, searchInsert(a, 4, 0));return 0;
}

http://www.ngui.cc/zz/2727422.html

相关文章

c++高级编程学习笔记3

函数指针的类型别名 我们通常不考虑函数在内存中的位置&#xff0c;但每个函数实际上都位于某个特定地址。在 C中&#xff0c;可像使用数据那样使用函数。换言之&#xff0c;可使用函数的地址&#xff0c;就像使用变量那样。函数指针的类型取决于兼容函数的参数类型的返回类型…

Qt例子学习笔记 - Examples/Qt-6.2.0/qt3d/basicshapes-cpp

main.cpp //基本形状显示了 Qt 3D 提供的四种基本形状&#xff1a;圆环、圆柱、立方体和球体。 //该示例还展示了如何将 Qt 3D 场景嵌入到小部件中并与其他小部件连接。#include "scenemodifier.h"#include <QGuiApplication> #include <Qt3DRender/qcame…

Qt例子学习笔记 - Examples/Qt-6.2.0/assistant/simpletextviewer

main.cpp #include "mainwindow.h"#include <QApplication> //QApplication 专门为 QGuiApplication 提供了一些基于 QWidget 的应用程序所需的功能。 // 它处理特定于小部件的初始化、完成。 //对于任何使用 Qt 的 GUI 应用程序&#xff0c;无论应用程序在任…

Qt例子学习笔记 - Examples/Qt-6.2.0/charts/customchart

//自定义图表 //我们首先创建一个简单的线系列和一个图表对象。 QLineSeries *series new QLineSeries();*series<<QPointF(0,6)<<QPointF(9,4)<<QPointF(15,20) << QPointF(25, 12) << QPointF(29, 26);QChart *chart new QChart();chart->…

跨平台编译项目

1.linux:INCLUDEPATH “” 2.linux: { message(linux) } 3.message($$QMAKESPAEC) xzxiaqiu:~/study/csdn/day0/test/build$ ls /opt/Qt/Qt6/6.2.0/gcc_64/mkspecs/ aix-g integrity-x86 macx-clang solaris-cc-64 aix-g-64 linux…

布局Layout

布局Layout 1.Vertical Layout 2.Horizontal Layout 3.Grid Layout 4.Form LayoutsizeHint推荐尺寸 1.QSize sizeHint() 推荐尺寸只能重载修改 2.QSize size() 不包含边框的窗口尺寸QSizePolicy::PolicyFlag 1.GrowFlag 必要时可超过推荐 2.ExpandFlag 尽可能的扩展 3.ShrinkF…

QTreeWidgetQTreeWidget

QTreeWidget 1.常用属性 2.标题设置 3.内容插入 4.内容选择 5.拖动和删除 6.信号事件 7.样式qss QTreeWidget 属性 1.header()->setVisible(true) 2.setSortingEnabled点击标题排序 3.setAnimated 动画展开 4.setVerticalScrollBarPolicy setHorizontalScrollBarPolicy滚动…

JDK 和 JRE 的区别

JRE(Java Runtime Enviroment) 是 Java 的运行环境。面向 Java 程序的使用者&#xff0c;而不是开发者。如果你仅下载并安装了JRE&#xff0c;那么你的系统只能运行 Java 程序。JRE 是运行 Java 程序所必须环境的集合&#xff0c;包含JVM标准实现及 Java 核心类库。它包括 Java…

通信__协议的那点事!!

我们的“协议”&#xff1a; 到目前为止&#xff0c;我们已经简单了解了通信的基本模型&#xff0c;Server—Client模型&#xff0c;这里以简单聊天工具为例&#xff1a;1、服务端启动——2、客户端启动&#xff0c;并试图与服务端建立连接——3、服务端根据条件&#xff08;通…

《Google三大论文》_The Google File System

关于预期和实现&#xff1a; 在Google的面向大规模的数据密集型的分布式运用中&#xff0c;GFS都是关键和基础。同时&#xff0c;开源的hadoop File System 与GFS也是很相似的。 与传统的文件系统相比&#xff0c;GFS在设计上有以下几种特点&#xff1a; 一、组件失效被认为是常…