Solution in Python


  • 0
    D

    This is a Binary Search problem: Finding an element in a sorted array
    The problem can be solved using Divide and Conquer approach
    1- Divide: Comparing the element (target) with the middle element of the array
    2- Conquer: Recursively search 1 subarray
    3- Combine: Trivial ( there is no additional computation for this part)

    Starting from the array,
    st is the first element of the array, en is the last element of the array.
    finding the median:
    st <= med <= en

    If target is >= than med, then target should be at the right subarray.
    if target is <= than med, then target should be at the left subarray.
    Here is the code

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

    Time Complexity: O(log n) : the recursive equation is T(n)= 1*T(n/2) + O(1). then time complexity can be calculated using substitution or master method.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.