插入位置

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

算法设计

设元素所在的位置(或最终需要插入的位置)为index, 在二分查找的过程中,index的更新方法: 如果target == nums[mid]:index = mid; 如果target < nums[mid],且 (mid == 0或 target > nums[mid-1]): index = mid; 如果target > nums[mid],且 (mid == nums.size() – 1 或 target < nums[mid+1]): index = mid + 1;

class Solution{
public:
    int searchInsert(std::vector<int> &nums, int target){
        int index = -1;//最终返回的下标,否则为需要插入的位置;
        int begin = 0;
        int end = noms.size() -1;
        while( index == -1){//若index == -1,则说明还未找到正确位置,持续二分搜索
            int mid == (begin + end) / 2;
            if(target ==nums[mid]){
                index = mid;
            }
            else if(target < nums[mid]){
                if(mid == 0 || target > nums[mid-1]){
                    index = mid;
                    }  
                 end = mid -1; 
             }
             else if(target > nums[mid] || mid == nums.size()-1){
                  if(target < nums[mid+1]){
                      return index = mid+1;
                  }
                  begin = mid +1 ;
              }
            
        }
        return index;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java3y

泛型就这么简单

1634
来自专栏Petrichor的专栏

python: copy库 与 list拷贝

1331
来自专栏听雨堂

JavaScript大略

 简介: javascript是一种基于对象和事件驱动并具有安全性能的脚本语言。 它是通过嵌入或调入在标准的HTML语言中实现的。 数据类型:   St...

18110
来自专栏测试开发架构之路

总结了一些指针易出错的常见问题(四)

指针与结构体 简介:我们可以使用C的结构体来表示数据结构元素,比如链表或树的节点,指针是把这些元素联系到一起的纽带。 typedef struct _pers...

2947
来自专栏aCloudDeveloper

经典排序之 插入排序

Author: bakari  Date: 2012.7.21 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之...

1988
来自专栏Java架构

面试必备:30 个 Java 集合面试问题及答案

Java集合框架为Java编程语言的基础,也是Java面试中很重要的一个知识点。这里,我列出了一些关于Java集合的重要问题和答案。

782
来自专栏cs

python的顺序程序设计

赋值 同步赋值:变量1,变量2,....变量n=表达式1,表达式2,.....表达式n 同步赋值首先计算右边n个表达式的值,然后同时将表达式的值赋给左边的n...

4226
来自专栏mathor

LeetCode46. 全排列

 标准dfs问题,只不过这道题有点麻烦在于返回的是一个List嵌套List  声明一些变量,首先是ans保存最终结果,其次是path[],存储当前选取的...

1287
来自专栏决胜机器学习

PHP数据结构(二十一) ——希尔排序

PHP数据结构(二十一)——希尔排序 (原创内容,转载请注明来源,谢谢) 一、概述 希尔排序,又称缩小增量排序,也属于插入排序类方法,时间上有较大改进。前面...

3467
来自专栏Python

while补充,字符串和数字的内置方法

一、while循环的补充 while True: name=input('please input your name: ') password...

2627

扫码关注云+社区

领取腾讯云代金券