【LeetCode】35.搜索插入位置

LeetCode35.搜索插入位置题解

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

• 输入: nums = [1,3,5,6], target = 5
• 输出: 2

示例 2:

• 输入: nums = [1,3,5,6], target = 2
• 输出: 1

示例 3:

• 输入: nums = [1,3,5,6], target = 7
• 输出: 4

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

解题思路

• 思路1：直接判断target和数组值大小，如果target小于等于当前的数组值，那就返回当前的下标，如果比对到最后一个数值，目标值大于数组的最后一个数值，那就返回数组大小的值，插入位置就是在最后一个元素后面插入了。
• 思路2：二分查找，懂思路，不想写……待更新！

code

1 暴力解法

vscode测试版本

#include <stdio.h>

int searchInsert(int* nums, int numsSize, int target)
{
    int ret;
    for(int i = 0; i <= numsSize; i++){
        if ( i < numsSize){
            if (target <= nums[i]){
                ret = i;
                break;
            }
        }
        else if ( i == numsSize){
            if (target > nums[i-1])
                ret = i;
        }
    }
    return ret;
}

int main()
{
    int nums[] = {1,3,5,6};   
    int array_size = sizeof(nums) / sizeof(int);    //数组的元素个数（这里注意要除以sizeof(int)）
    printf("array_size = %d\n", array_size);
    int target = 7;
    int ret = searchInsert(nums, array_size, target);
    printf("ret = %d\n", ret);
    return 0;
}

暴力解法，力扣提交版本

int searchInsert(int* nums, int numsSize, int target)
{
    int ret;
    for(int i = 0; i <= numsSize; i++){
        if ( i < numsSize){
            if (target <= nums[i]){
                ret = i;
                break;
            }
        }
        else if ( i == numsSize){
            if (target > nums[i-1])
                ret = i;
        }
    }
    return ret;
}		

2 二分查找

什么是二分查找？

二分查找，又称为折半查找，是一种在有序数组中查找指定目标的搜索算法。该算法通过将目标值与数组中间的元素进行比较来逐步缩小搜索范围，直到找到目标元素或发现其不存在为止。

二分查找的原理

二分查找的基本原理如下： 1、确定要查找区间的左右端点 left 和 right；
2、计算中间位置 mid = (left + right) / 2；
3、比较中间位置 mid 的值和要查找的目标值 target：
（1）如果 mid 的值等于目标值 target，则找到了目标值；
（2）如果 mid 的值大于目标值 target，则在左半边的区间 [left, mid-1] 继续查找；
（3）如果 mid 的值小于目标值 target，则在右半边的区间 [mid+1, right] 继续查找；
4、重复上述步骤，直到找到目标元素或者区间不存在为止。

简单来说就是每次找到区间的中位数，判断该中位数是否是目标值，若不是则确定新的区间范围再寻找其中位数。以此类推，直到找到目标值为止。

二分查找图解

二分查找的优缺点

优点：
1、时间复杂度为O(logn)，是一种非常高效的查找算法。
2、 可以应用于静态数组和有序链表中，在已经排好序的序列中进行二分查找具有相当高的性能，比如可以在很大的数据集合中快速地定位某一元素。
缺点：
1、要求待查找的序列必须是有序的。如果不是有序的，则需要先排序，增加时间和空间复杂度。
2、数组大小是固定的，不能动态调整。如果数据量较大，就需要占用更多的内存空间来存储。
3、只适用于单个元素的查找，对于区间查找、前缀匹配等问题无法直接使用。
4、当数组中存在重复元素时，查找结果可能不是唯一的，需要对查找结果进行处理。
————————————————

                        版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/ikun10001/article/details/130208926

……更新中