lintcode 60. Search Insert Position

class Solution { public: /** * @param A: an integer sorted array * @param target: an integer to be inserted * @return: An integer */ int searchInsert(vector<int> &A, int target) { // write your code here // search the first element that >= target int sizeA = A.size(); if(sizeA == 0){ return 0; } if(A[0] >= target){ return 0; } if(A[sizeA - 1] < target){ return sizeA; } int start = 0; int end = sizeA - 1; while(start + 1 < end){ int mid = (start + end) / 2; if(A[mid] >= target){ end = mid; } else{ start = mid; } } if(A[start] == target){ return start; } if(A[end] == target){ return end; } if(A[start] < target && A[end] > target){ return end; } } };

二刷
2019年03月30日11:04:12
int searchInsert(vector<int> &A, int target) { // write your code here // 找到比target大的最小的值 const int n = A.size(); if(n == 0){ return 0; } int start = 0; int end = n - 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; } }