# [LeetCode] Top Interview 150 Problems Solving # 35 Search Insert Position

# **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.
    

```python
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.