力扣：搜索插入位置代码实现

题目

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

请必须使用时间复杂度为 O(log n) 的算法。

 python实现

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
    
        while left <= right:
            mid = (left + right) // 2  # 计算中间位置
            if nums[mid] == target:
                return mid  # 找到目标值，返回索引
            elif nums[mid] < target:
                left = mid + 1  # 调整左边界
            else:
                right = mid - 1  # 调整右边界

        # 如果没有找到目标值，则此时 left 是目标值应插入的位置
        return left

C代码实现

#include <stdio.h>

// 二分查找函数
int search_insert(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止(left + right)溢出

        if (nums[mid] == target) {
            return mid; // 找到目标值，返回索引
        } else if (nums[mid] < target) {
            left = mid + 1; // 目标值在右半部分
        } else {
            right = mid - 1; // 目标值在左半部分
        }
    }

    // 如果没有找到目标值，则此时 left 是目标值应插入的位置
    return left;
}

int main() {
    int nums[] = {1, 3, 5, 6};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int targets[] = {5, 2, 7, 0};
    int targetsSize = sizeof(targets) / sizeof(targets[0]);

    for (int i = 0; i < targetsSize; ++i) {
        printf("Target %d should be at index: %d\n", targets[i], search_insert(nums, numsSize, targets[i]));
    }

    return 0;
}