[toc]

**Company tags: Adobe, Uber, Airbnb, Bloomberg**

Are you looking to ace your coding interview? If yes! Then this question is one the must-do for you as it has been reportedly asked in numerous interviews by some of the giant organizations like Adobe. Can you solve this problem optimally?

**Problem Statement**

Given a **sorted array** of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

**Challenge:** Can you propose an algorithm with** O(log n)** runtime complexity?

⚠️**Constraints:**

`1 <= nums.length <= 104`

`-10`

^{4}<= nums[i] <= 10^{4}`nums`

contains distinct values sorted in*“ascending order”*.`-10`

^{4}<= target <= 10^{4}

**Examples**

Let us look at some examples to improve the understanding of the problem:

Example 1:Input: nums = [1, 3, 5, 6] target = 5 Output: 2 Explanation: Target 5 is indexed at position 2 in the array. Example 2:Input: nums = [1, 3, 5, 6] target = 2 Output: 1 Explanation: Target 2 will be inserted at position 1 in the array. Example 3:Input: nums = [1, 3, 5, 6] target = 7 Output: 4 Explanation: Target 7 will be inserted at position 4 in the array. Example 4:Input: nums = [1, 3, 5, 6] target = 0 Output: 0 Explanation: Target 0 will be inserted at position 0 in the array. Example 5:Input: nums = [1] target = 0 Output: 0 Explanation: Target 0 will be inserted at position 0 in the array. |

Now that you have a clear understanding of the problem, let’s dive into various methods to solve the problem:

**Method 1: Linear search**

**Approach: **The most straightforward way to solve the problem would be to iterate through every number in the array. Return the index if the target gets found. Else, check where the target value could be inserted and return that index value.

**Algorithm:**

- Check if the array is empty. If yes, return
`0`

. - If the target value is greater than the last element in the array, then the target value would get inserted at the end of the array. Hence, return the length of the array.
- If the target value is smaller than the first element in the array, the target would be inserted at the beginning of the array. Hence, return
`0`

. - Further, traverse the array. If the current number is greater than or equal to the target value, return the current index.

**Solution:**

def search_insert(nums, target): if not nums: return 0 if target > nums[-1]: return len(nums) if target < nums[0]: return 0 for i in range(len(nums)): if nums[i] >= target: return i

**Test Case Analysis:**

Let’s run this solution on our examples:

# Example 1nums = [1, 3, 5, 6] target = 5 print(search_insert(nums, target)) # 2 # Example 2nums = [1, 3, 5, 6] target = 2 print(search_insert(nums, target)) # 1 # Example 3nums = [1, 3, 5, 6] target = 7 print(search_insert(nums, target)) # 4 # Example 4nums = [1, 3, 5, 6] target = 0 print(search_insert(nums, target)) # 0 # Example 5nums = [1] target = 0 print(search_insert(nums, target)) # 0 |

Yeah! It passed all the test cases.

**Complexity Analysis:**

**Time Complexity**: In the worst-case scenario, you have to visit every number in the array. Hence, the time complexity of this method is**O(n)**.**Space Complexity:**No extra space is used. Hence, the space complexity of this method is**O(1)**.

**Discussion: **Though this algorithm fetches us the required output, however, it does not ensure that the runtime complexity is log(n) which is also a challenge presented to us. In the next approach, we will find out how to use binary search and reach the optimal solution.

**Method 2: Binary search**

**Approach: **A better approach would be to use binary search as you will be searching for a particular element in the array. You have to initialize two-pointers and calculate the value of `mid`

. Compare the mid-value with the target value and return the index if found.

**Algorithm:**

- Check if the array is empty. If yes, return
`0`

. - Initialize the variables low and high with
`0`

and`len(nums)`

, respectively. - While the “
`low`

” index is less than “`high`

”, calculate the mid-value. - Compare the mid-value with the target value.
- If the target value is greater than the mid-value, then the target value will be to the right. Update
`low`

to`mid + 1`

. - Else, if the target value is less than or equal to the mid-value, update
`high`

to`mid`

. - When you exit the loop, the position of the
`low`

pointer is either at the position equal to the target value or at the position where you have to insert the target value. Thus, return the value pointed by`low`

.

**Consider the following illustration to understand the approach better:**

**Solution:**

def search_insert(nums, target): if not nums: return 0 low, high = 0, len(nums) while low < high: mid = (low + high) // 2 if target > nums[mid]: low = mid + 1 else: high = mid return low

**Test Case Analysis:**

Let’s run this solution on our examples:

# Example 1nums = [1, 3, 5, 6] target = 5 print(search_insert(nums, target)) # 2 # Example 2nums = [1, 3, 5, 6] target = 2 print(search_insert(nums, target)) # 1 # Example 3nums = [1, 3, 5, 6] target = 7 print(search_insert(nums, target)) # 4 # Example 4nums = [1, 3, 5, 6] target = 0 print(search_insert(nums, target)) # 0 # Example 5nums = [1] target = 0 print(search_insert(nums, target)) # 0 |

Yeah! It passed all the test cases.

**Complexity Analysis:**

**Time Complexity:**As this method uses binary search, you have to traverse only half the array. Hence, the time complexity of this method is**O(log(n))**.**Space Complexity:**No extra space is used. Hence, the space complexity of this method is**O(1)**.

Do you want to develop the skills of a **well-rounded Python professional**—while getting paid in the process? Become a Python freelancer and order your book **Leaving the Rat Race with Python** on Amazon (*Kindle/Print*)!

**Bonus Method: Using Bisect Module**

**Approach: **You can use the **Bisect module** directly to find the position of the target element. The `bisect_left`

method of the bisect module is used to find the index of the target element in the sorted array. If the element is already present in the array then the leftmost position where the element can be inserted within the list gets returned.

**Bisect Module Recap:**

➥ The purpose of the **Bisect **algorithms is to find the **index/position** of a required element within a given list where the element has to be inserted within the list. Therefore, it helps to keep the list sorted after the insertion is complete.

➥ `bisect_left`

method of the bisect module is used to find the index of the target element in the sorted list. If the element is already present in the list then the leftmost position where the element can be inserted within the list is returned.

**Solution:**

from bisect import bisect_left def search_insert(nums, target): return bisect_left(nums, target)

**Test Case Analysis:**

Let’s run this solution on our examples:

# Example 1 nums = [1, 3, 5, 6] target = 5 print(search_insert(nums, target)) # 2 # Example 2 nums = [1, 3, 5, 6] target = 2 print(search_insert(nums, target)) # 1 # Example 3 nums = [1, 3, 5, 6] target = 7 print(search_insert(nums, target)) # 4 # Example 4 nums = [1, 3, 5, 6] target = 0 print(search_insert(nums, target)) # 0 # Example 5 nums = [1] target = 0 print(search_insert(nums, target)) # 0 |

Yeah! It passed all the test cases.

**Complexity Analysis:**

**Time Complexity:**As this method is similar to binary search, the time complexity of this method is O(log(n)).**Space Complexity:**No extra space is used. Hence, the space complexity of this method is O(1).

**Conclusion**

I hope you enjoyed this **coding interview** question. Please **stay tuned** and **subscribe** for more interesting coding problems.

**Post Credits: **Shubham Sayon and Rashi Agarwal

**Recommended: ****Finxter Computer Science Academy**

- One of the most sought-after skills on Fiverr and Upwork is
**web scraping**. Make no mistake:is a critical life skill in today’s world that’s shaped by the web and remote work.**extracting data programmatically from websites** - So, do you want to master the art of web scraping using Python’s BeautifulSoup?
- If the answer is yes – this course will take you from beginner to expert in Web Scraping.