面试经典150题 P35 搜索插入位置

---

时间轴

时间轴

2025-12-02

init

分治

---

题目：

P35 搜索插入位置

https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-interview-150

二分，注意边界

#include <vector>
using std::vector;

class Solution {
    public:
	int searchInsert(vector<int> &nums, int target)
	{
		int left = 0, right = nums.size() - 1;
		int mid = 0;
		while (left <= right) {
			mid = (left + right) / 2;
			if (nums[mid] == target) {
				return mid;
			} else if (nums[mid] < target) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		if (nums[mid] > target) {//边界
			return mid;
		} else {
			return mid + 1;
		}
	}
};

leetcode hot 100 rewrite

#include <vector>
using std::vector;

class Solution {
    public:
        int searchInsert(vector<int> &nums, int target)
        {
                int n = nums.size();
                int left = 0, right = n - 1, mid = 0;

                while (left <= right) {
                        mid = left + (right - left) / 2;

                        if (nums[mid] < target)
                                left = mid + 1;
                        else if (nums[mid] > target)
                                right = mid - 1;
                        else
                                return mid;
                }

                return left; // right < left
        }
}