35. Search Insert Position

Description:

https://leetcode.com/problems/search-insert-position/#/description

Algorithm:

The searching for middle is the classic method.

Searching for the insert index will be the left.

Code:

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if (nums.empty()) return 0;
int n = nums.size();
int left = 0, right = n – 1;
int middle;

while (left <= right)
{
middle = (left + right) / 2;
if (nums[middle] == target)
return middle;
else if (nums[middle] < target)
left = middle + 1;
else
right = middle – 1;
}
return left;
}
};

Timing:

O(logn)