# Solution in Python

• 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.

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