Cover image for Interview Classic 150 Questions P35 Search Insert Position

Interview Classic 150 Questions P35 Search Insert Position

(Updated: )
algorithm
, , ,
Timeline

Timeline

2025-12-02

init

Divide and Conquer

Title:

P35 Search Insert Position

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

Binary search, pay attention to boundaries

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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
        }
}