class Solution {

public:

int insertInOrder(vector<int>& arr, int target){

int low = 0, high = arr.size() - 1;

while(low <= high){

int mid = low + (high - low) / 2;

if(arr[mid] <= target && arr[mid + 1] >= target)

return mid + 1;

else if(target <= arr[mid] && mid == 0)

return 0;

else if(target >= arr[mid] && mid == arr.size() - 1)

return arr.size();

else if(target < arr[mid])

high = mid - 1;

else

low = mid + 1;

}

}

public:

int binarySearch(vector<int>& arr, int target){

int low = 0, high = arr.size() - 1;

while(high > low){

int mid = low + (high - low) / 2;

if(arr[mid] == target)

return mid;

else if(target < arr[mid])

high = mid - 1;

else

low = mid + 1;

}

return -1;

}

public:

int searchInsert(vector<int>& nums, int target) {

int index = binarySearch(nums, target);

if(index != -1)

return index;

else

return insertInOrder(nums, target);

}

};