Classic Interview 150 Questions P35 Search Insert Position

---

Timeline

Timeline

2025-12-02

init

Divide and Conquer

---

Problem:

P35 Search Insert Position

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

Binary search, mind the boundaries

#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) {//Boundary
			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
        }
}