Search Insert Position

• median
• tag: array, binary search
• similar:

找到插入target的位置使得保持有序性

思考

• 这题本身很简单. 最主要的问题是: 是否一直使用九章的模版?
  • template还是重要的. 因为这本身就是避免了corner case.

idea 0:

• 一时头晕, 居然没用binary search而是O(n)的search.

idea 1:

• 我使用的binary search模版, 但是最后如何判断呢, 有点乱. 所以错了. 这里贴上正确的代码:

if (A == null || A.length == 0) {
      return 0;
    }
    int start = 0, end = A.length - 1;

    while (start + 1 < end) {
      int mid = start + (end - start) / 2;
      if (A[mid] == target) {
        return mid;
      } else if (A[mid] < target) {
        start = mid;
      } else {
        end = mid;
      }
    }

    // 我一开始这个地方头晕了. 上面的部分还是用的模版. 下面是重点部分. 这里是找到第一个比它大的数.
    if (A[start] >= target) { 
      return start;
    } else if (A[end] >= target) {
      return end;
    } else {
      return end + 1;
}