store/works/solutions/leetcode/cpp/35.cpp


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
27
28
29
30
31
32
33
34
35
36

#include <vector>

using std::vector;

class Solution
{
public:
    int searchInsert(vector<int> &nums, int target)
    {
        if (nums.empty())
            return 0;

        int left_index = 0;
        int right_index = nums.size();

        while (left_index != right_index)
        {
            const int middle_index = (left_index + right_index) / 2;
            const int middle_value = nums[middle_index];
            if (target < middle_value)
            {
                right_index = middle_index;
            }
            else if (target > middle_value)
            {
                left_index = middle_index + 1;
            }
            else
            {
                return middle_index;
            }
        }

        return left_index;
    }
};