首页 > 二分法：search insert position 插入位置

二分法：search insert position 插入位置

问题描述：

给定一个排序数组nums(无重复元素)与目标值target，如果target在nums里 出现，则返回target所在下标，如果target在nums里未出现，则返回target应该 插入位置的数组下标，使得将target插入数组nums后，数组仍有序。

例如：

数组 arr = [2,3,4,6]

target = 1时， 插入位置应为 index = 0

target = 5时，插入位置应为 index = 3

target = 3时，下标就变为index = 1

这里我们分析：

  1. 查找时我们仍然使用正常的二分查找，关于二分查找的递归和非递归实现可以参考二分法：二分查找（递归+非递归）实现
  2. 假如我们找到了target，那么index = mid
  3. 如果arr[mid] > target且 (mid == 0 或者 arr[mid -1] < target)

    index = mid - 1

    这个就是将mid卡在一个范围内，比如[2,4,5,6]中查找3，arr[1] > 3但是arr[0] < 3
  4. 如果arr[mid] < target 且(mid == arr.size() - 1 或者 arr[mid + 1] > target)

    这同样时将mid卡在另一个上升区间，比如[2,3,4,6]中查找5,arr[2]<5,但是arr[3]>5

    此时index = mid + 1

综上，我们可以写出如下实现过程

int find_part(std::vector<int> &arr, int target) { int begin = 0;int end = arr.size() - 1;int mid = (begin + end) / 2;int index = -1;while(index == -1) { if (arr[mid] == target) { index = mid; } else if (arr[mid] > target) { //左区间if (mid == 0 || target > arr[mid - 1]) { index = mid;//target比数组开头小，保证target是插入到了0}end = mid - 1; //缩小mid范围}else if (arr [mid] < target) {  //右区间if (mid == (arr.size() - 1) || target < arr[mid + 1]) { index = mid + 1;}begin = mid + 1;}mid = (begin + end) / 2;}return index;
}

测试代码如下:

#include 
#include using namespace std;int find_part(std::vector<int> &arr, int target) { int begin = 0;int end = arr.size() - 1;int mid = (begin + end) / 2;int index = -1;while(index == -1) { if (arr[mid] == target) { index = mid;} else if (arr[mid] > target) { if (mid == 0 || target > arr[mid - 1]) { index = mid; //target比数组开头小，保证target是插入到了0}end = mid - 1;}else if (arr [mid] < target) { if (mid == (arr.size() - 1) || target < arr[mid + 1]) { index = mid + 1;}begin = mid + 1;}mid = (begin + end) / 2;}return index;
}
int main() { std::vector<int> arr1;int n;cin >> n;for (int i = 0;i < n; ++i) { int tmp;cin >> tmp;arr1.push_back(tmp);}int target;cin >> target;cout << find_part(arr1, target);return 0;
}

输出如下:

#输入
5
2 3 4 5 6
1
#输出
0

更多相关：

  • 二分法：查找区间search for a range

    问题描述： 给定一个排序数组nums(nums中有重复元素)与目标值target，如果 target在nums里出现，则返回target所在区间的左右端点下标，[左端点, 右端点]，如果target在nums里未出现，则返回[-1, -1]。 例如: arr = [2,3,4,4,4],target = 4,最终结果为[2,4] a...

  • 75. Find Peak Element 【medium】

    75. Find Peak Element 【medium】 There is an integer array which has the following features: The numbers in adjacent positions are different.A[0] < A[1] && A[A.length...

  • 367. Valid Perfect Square

    题目： Given a positive integer num, write a function which returns True if num is a perfect square else False. Note: Do not use any built-in library function such as sqrt...

  • 数据结构（1）有序表查找

     有序表查找 /* 主函数 */public class OrderTableSearch {public static void main(String[] args) {int [] a= {0,1,16,24,35,47,59,62,73,88,99}; System.out.println(FibonacciSearc...

  • 剑指offer：面试题04. 二维数组中的查找

    题目：二维数组中的查找 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 示例: 现有矩阵 matrix 如下： [[1, 4, 7, 11, 15],[2, 5, 8, 12, 1...

  • valgrind 使用 kcachegrind 查看函数运行时间

    安装 首先安装运行分析函数时间的工具 kcachegrind 下载安装包 http://kcachegrind.sourceforge.net/，下载最新的 tar.gz 文件 解压文件，进入解压之后的目录，从 README 中可以找到安装方式，这里记录一下 cmake . make -j8 sudo make install...

  • Linux ISCSI配置

    一、简介 iSCSI（internet SCSI）技术由IBM公司研究开发，是一个供硬件设备使用的、可以在IP协议的上层运行的SCSI指令集，这种指令集合可以实现在IP网络上运行SCSI协议，使其能够在诸如高速千兆以太网上进行路由选择。iSCSI技术是一种新储存技术，该技术是将现有SCSI接口与以太网络(Ethernet)技术结合，使...

  • 记录CSS3 target伪类简介

    CSS3 target伪类是众多实用的CSS3特性中的一个。它用来匹配文档(页面)的URI中某个标志符的目标元素。具体来说，URI中的标志符通常会包含一个”#”字符，然后后面带有一个标志符名称，比如#respond，target就是用来匹配ID为respond的元素的。 现在在页面中，点击一个ID链接后，页面只会跳转到相应的位置，但...

  • flash玩转cookie

    经常有遇到说浏览器与flash之间不好debug,数据不好交流，确实每次遇到都得多写些代码。麻烦！ 这回我打算写个flash类，专门用来解决这些问题。这几天，我就先从cookie的读写开始，写了个cookie类，有了这个类，以后我就能直接在flash里面操作cookie了。一劳永逸，大伙如果觉得有用就拿去吧。我已经放在了google...

  • 剑指offer: 面试题40. 最小的k个数

    题目：最小的k个数 入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 示例 1： 输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1] 示例 2： 输入：arr = [0,1,2,1], k = 1 输出：[0...

  • JS如何深度复制对象和数组，避免指针变量引用修改值

    //自定义深度复制对象or数组的递归方法---------------------------------------- let copyObjOrArr = o => {let isArray = o instanceof Array;let isObject = o instanceof Object;if (!isObject)...

  • 【数组方法大合集】原生js数组array常用工具方法大合集

    var array = {/* 数组求和*/sum: arr => eval(arr.join("+")),/* 判断一个数组(支持一个字符串)里面的是否有任何一个元素被包含在了某个字符串里面 */isStringContain(str, arr) {Array.isArray(arr) || (arr = [arr]);for (v...

  • 快速排序的两种实现方法(c语言版本)

    经过调研发现，对任意无序整数数组，快速排序有两种实现方法，这里简单阐述下思路： 思路一：随意选择一个基准元，一般选择数组的起始元或末尾元，Weiss这本书上特意搞了个算法来选择基准元，……，总之就是基准元的选择要尽量随机。选定基准元之后，比如选择数组起始元为基准元，从数组右边开始，向左边遍历，遇到比基准元大的跳过，直至遇到比基准元小...

  • 十种经典排序算法精粹(c语言版本)

    下面给出这段时间我苦心研究验证过的十种经典排序算法的C语言版本，即下面的排序算法： 插入排序，shell排序，冒泡排序，快速排序，选择排序，堆排序，归并排序，桶排序，基数排序和计数排序。整理出来以作备忘，不足之处，欢迎大家批评指正！其中计数排序分别给出了不稳定和稳定两种排序算法，测试时，使用随机生成大数组和随机手动输入的方法来测试。...

©2024 11GX.COM