35. Search Insert Position

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.

You must write an algorithm with O(log n) runtime complexity.

\

Solution:

• This is a sorted array with distinct integers, and the question require us to solve with O(logn) time complexity
• Considering to solve this problem with Binary Search
• The place we want to insert is where the first element that greater than target is
• If no such element, insert the element to the end of this array

class Solution:
		def searchInsert(self, nums: List[int], target: int) -> int:
				left, right = 0, len(nums) - 1
				while left <= right:
						mid = (left + right) // 2
						if nums[mid] == target:
								return mid
						elif nums[mid] < target:
								left = mid + 1
						elif nums[mid] > target:
								right = mid - 1
				return left

74. Search a 2D Matrix

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

\

My solution:

• Consider this is an row sorted matrix and the first integer of the row is greater than the last integer of the previos row
• We can first find which row the integer will be likely belong to:
  • It should geq to the first element of the row, and less than the first element of the next row
  • If it less than the first element of the first row, then it won’t appear in the whole matrix
  • To achieve this, we can use a binary search on the first element of each row