Leetcode: Search Insert Position

Search Insert Position | LeetCode OJ

Given a sorted list and a value, we need to find the index where it should be inserted or return the index at which it is already present. Searching in a sorted list should always be done using binary search. The steps are listed below

1. Find the middle element of the list
2. If value matches with target then return the index
3. If value is greater than target, we need to search the left half
4. Otherwise we need to search the right half

To code the above logic

1. Use pointers low and high to define the range of search
2. Initialize low with 0 and high with length of array
3. Initialize mid with average of low and high
4. To search in left half move high pointer to mid and recalculate mid
5. To search in right half move the left pointer to mid and recalculate mid
6. Continue till mid equals low at which point further iterations will keep on pointing mid to low

Remarks

1. O(log n) time complexity for using divide and conquer technique
2. O(1) space complexity as only 3 additional variables are used
3. Integer overflow is prevented by using the expression (high-low) instead of (high+low). This is not applicable to python as python converts int to long as per the need.
4. The result of low+(high-low)/2 will never be equal to high, it can at most reach high-1. Hence we initialize high with length of list to reach the last valid index which is one less than the length of list

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        low, high = 0, len(nums)
        mid = low + (high - low) / 2
        while mid != low:
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                low = mid
            else:
                high = mid
            mid = low + (high - low) / 2
        return mid if target <= nums[mid] else mid + 1

This code is useful for solving a variety of problems. You might need to change the condition at which it returns or call it multiple times.

1. Search in rotated array
2. Search for a range
3. Find minimum in rotated sorted array
4. Valid Perfect Square