leetcode35：搜索插入位置

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

void printArray(const vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
}

/*
    二分，查找大于等于目标值的第一个位置。

    时间复杂度：O(logn)
*/
class Solution_0 {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size();

        while (l < r) {
            int mid = l + r >> 1;
            // if (nums[mid] >= target) r = mid;
            // else l = mid + 1;
            if (nums[mid] == target) r = mid;
            else if (nums[mid] < target) l = mid + 1;
            else if (nums[mid] > target) r = mid;
        }

        return r; // 结束条件：l == r
    }
};

/*
    思路同上

    参考：https://labuladong.online/algo/essential-technique/binary-search-framework/
*/
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                right = mid - 1; // 别返回，锁定左侧边界
            }
        }

        return left;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {1, 3, 5, 6};
    printArray(nums);
    int target = 5;
    int result = solution.searchInsert(nums, target);
    cout << "Insertion index for target " << target << " is: " << result << endl;

    return 0;
}

Golang 代码

package main

import (
	"fmt"
	"reflect"
)

/*
   二分查找算法：
       使用二分查找法在排序数组中查找目标值或确定其插入位置。
       如果目标值等于中间元素，直接返回索引。
       如果目标值大于中间元素，调整左边界；如果目标值小于中间元素，调整右边界。
       当 left > right 时，left 即为目标值的插入位置。

    时间复杂度：O(logn)
        二分查找：每次迭代将搜索范围缩小一半，因此时间复杂度为 O(logn)，其中 n 是数组的长度。
    空间复杂度：O(1)
        常数空间：仅使用了两个指针 left 和 right，空间复杂度为 O(1)。
*/
// searchInsert 返回目标值在排序数组中的索引，如果不存在则返回插入位置
func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums) - 1
	for left <= right {
		mid := left + (right - left) / 2
		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return left
}

func main() {
	// 测试用例
	testCases := []struct {
		nums      []int
		target    int
		expected  int
	}{
		{[]int{1, 3, 5, 6}, 5, 2},   // 目标值在数组中
		{[]int{1, 3, 5, 6}, 2, 1},   // 目标值不在数组中，插入到中间
		{[]int{1, 3, 5, 6}, 7, 4},   // 目标值不在数组中，插入到末尾
		{[]int{1, 3, 5, 6}, 0, 0},   // 目标值不在数组中，插入到开头
		{[]int{}, 1, 0},             // 空数组
	}

    for i, tc := range testCases {
        fmt.Printf("Test Case %d, Input: nums = %v, target = %d\n", i+1, tc.nums, tc.target)
		result := searchInsert(tc.nums, tc.target)

        if reflect.DeepEqual(result, tc.expected) {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
        }
	}
}