Understanding the Problem

This should be a typical binary search algorithm problem. This problem is meticulous about the time efficiency as this has to be solved with the time complex of O(log n).

There is a number target as an integer. It is to find the right spot for target to be in the list nums, where numbers are sorted low to high like [1, 3, 6, 7]. If target = 2, the returned value should be 1, as target should be in between 1 and 3, which has the index 1 as the position.

Approach

Binary search has not been considered by me. I have always dealt with sorting problems with sorted() function and search problems with index() or find() methods.

My idea was to solve this problem with finding the middle as half and slicing the list down as the loop goes on and on. This was completely a wrong approach, because I would not be able to find the index with it.

The final approach was to update left and right values with index. I had a little help by a LLM though.

Solution

The solution with left and right as index approach mitigated the complexity of the code.

1. First, left and right was set with index values, the beginning and the end of the list.

2. In while loop, it will be stopped if left meets right so it will not be processed any further even when left is bigger than right

3. Take half to get the value in the middle. if target is equal to the value nums[half], return the index value half.

4. If target is greater than nums[half], left is updated by adding half + 1. It is to jump the index to the half so the binary approach is applied. + 1 is added though, because of index difference

   • For instance, imagine the list is nums = [1, 3, 5, 7] and target is 6. In the first loop, half will be (0 + 3) // 2, which will be 1.

   • target is greater than nums[half], which is 3, so update left with left = 1 + 1, to make it to 2 so it will start from index 2.

   • Then this time only nums = [5, 7] will be considered.

5. In other cases, update right to stick with the left half.

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            half = (left + right) // 2
            if target == nums[half]:
                return half
            elif target > nums[half]:
                left = half + 1
            else:
                right = half -1
        return left

Reflection

From my perspective, algorithm problems often require searching methods with good time complexity. Binary search with time complexity of O(log n) is very typical and I should be familiar with it. The key is to use index values other than dealing with the actual list and slicing.