Use of Search Insert Position Test
The solution approach of the problem is to use binary search. Initializes two variables, lo and hi, which represent the lower and upper bounds of the search range, respectively. Initially, lo is set to 0 (the first index) and hi is set to nums.size() - 1 (the last index). Use a while loop to perform a binary search within the search range (lo to hi) until lo becomes greater than hi. This indicates that the search range is exhausted, and the target should be inserted at index lo. Inside the while loop, the calculates the middle index mid using the formula lo + (hi - lo) / 2. This formula ensures that the midpoint is always closer to the lower bound in case of an even-sized range. If the value at the middle index (nums[mid]) is equal to the target value. If it is, the target value is found, and the function returns mid as the index of its occurrence. If nums[mid] is greater than the target value, it means the target should be inserted in the left half of the search range. Therefore, the code updates hi to mid - 1 to narrow down the search range to the left half. If nums[mid] is less than the target value, it means the target should be inserted in the right half of the search range. Therefore, the code updates lo to mid + 1 to narrow down the search range to the right half. The while loop continues to iterate and perform the binary search until lo becomes greater than hi. If the while loop exits without finding the target value, it means the target value is not present in the array. In this case, the code returns lo, which represents the index where the target should be inserted to maintain the sorted order.
