今回は説明文に「昇順にソート済みの配列が与えられる」旨の記載があるので、2分探索を使用します。
（O(log n)のアルゴリズムを使ってねとも書いてあります。）
再帰を使用する方法
class Solution {
public:
int searchInsert(const vector<int>& nums, int target) {
if (nums.size() <= 1) {
return nums.empty() || target <= nums.front() ? 0 : 1;
}
const size_t mid = nums.size() / 2;
if (nums[mid] == target) {
return mid;
}
return target < nums[mid]
? searchInsert(std::vector<int>(nums.cbegin(), nums.cbegin() + mid), target)
: mid+1 + searchInsert(std::vector<int>(nums.cbegin() + mid+1, nums.cend()), target);
}
};真ん中の要素がtargetと一致するか、見ている配列の要素数が1以下になるまで比較し続けます。
再帰呼び出しする際に std::vector の右辺値を渡しているため、引数の定義には const 修飾が必要になります。
時間計算量、空間計算量は、共に O(log n) です。
繰り返し構文を使用する方法
class Solution {
public:
int searchInsert(const vector<int>& nums, int target) {
int begin = 0;
int end = nums.size() - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
if (nums[mid] == target) {
return mid;
}
if (target < nums[mid]) {
end = mid - 1;
} else {
begin = mid + 1;
}
}
return begin;
}
};時間計算量は O(log n) 、空間計算量は O(1) です。
再帰処理はスタックを消費するので、メモリ的にはこちらの方が効率は良いはずです。
(LeetCode上では誤差程度しか変わりませんでしたが……)
以上です！