```
class Solution {
public:
int searchInsert(int A[], int n, int target) {
int left = 0;
int right = n-1;
int mid = left + right >> 1;
int pos = -1;
int flag = 1; // if not found, it will be mid + 1
while (left <= right){
if (A[mid] < target){
left = mid + 1;
pos = mid;
}
else if (A[mid] > target) { // when target < A[0], right = -1, then mid = -1, flag is still 1
right = mid - 1;
pos = mid;
}
else {
pos = mid;
flag = 0;
break;
}
mid = left + right >> 1;
}
return mid + flag;
}
};
```