search insert position.png
===================== 解題思路 =====================
一開始單純想著直接暴力解掃整個 vector, 暴力解法就是 O(n) 時間複雜度, 但題目要求的是 Ｏ（logn) 所以看到 logn 可以直接考慮 binary search 了 基本的 BS 題型, 這類題大致都符合 while(L +1 < R) 的模式, 可以避免進入死循環(huán) 最終在檢查三個位置 L 左邊 , L 跟 R 之間 以及 R 右邊即可
===================== C++ code ====================
<pre><code>
class Solution {
/**
* param A : an integer sorted array
* param target : an integer to be inserted
* return : an integer
*/
public:
int searchInsert(vector<int> &A, int target) {
// write your code here
if(A.size() == 0) return 0;
int L = 0, R = A.size() -1;
while(L + 1 < R)
{
int mid = L + (R - L) / 2;
if(A[mid] == target) return mid;
else if (A[mid] > target) R = mid;
else L = mid;
}
if(A[L] >= target) return L;
if(A[R] >= target) return R;
return A.size();
}
};
<code><pre>
