Search Insert Position

searchInsert.cpp

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        int low = 0, high = n;
        // search in the interval A[low, high)
        while (low < high) {
            // loop invariant
            // 1) 0 <= low < high <= n
            // 2) (low == 0 || A[low - 1] < target)
            // 3) (high == n || A[high] > target)
            auto mid = (high - low) / 2 + low;
            if (A[mid] < target) {
                low = mid + 1;
            } else if (A[mid] > target) {
                high = mid;
            } else {
                return mid;
            }
        }
        
        return low;
    }
};