LeetCode. Search Insert Position [Binary Search]

Problem:

Given a sorted array 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 may assume no duplicates in the array.

 

Example 1:

Input: [1,3,5,6], 5

Output: 2

 

Example 2:

Input: [1,3,5,6], 2

Output: 1

 

Example 3:

Input: [1,3,5,6], 7

Output: 4

 

Example 4:

Input: [1,3,5,6], 0

Output: 0

 

-Summary-

1. if the target number is in the nums list, we return the index of the target number. (Using .index() method)

2. else we find the correct position of the target number within the loop.

 

코드가 약간 정리가 잘 안된 느낌이다. 문제는 풀었지만, 다른 사람들의 풀이 방식을 보니, 더 깔끔하고 정리되 있었다. 또한 binary search 로 더 효율성 있게 풀수 있었던 문제였다. 오늘도 discussion을 보면서 많이 배운다.

 

Below is the more concise and clear solution for linear search and binary search solution.

-Linear Search-

leetcode.com/problems/search-insert-position/discuss/15425/Share-my-Python-solution

class Solution:
    # @param A, a list of integers
    # @param target, an integer to be inserted
    # @return integer
    def searchInsert(self, A, target):
		for i in range(len(A)):
			if A[i]>=target:
				return i
		return i+1

-Binary Search-

leetcode.com/problems/search-insert-position/discuss/15378/A-fast-and-concise-python-solution-40ms-binary-search

def searchInsert(self, nums, target):
    l , r = 0, len(nums)-1
    while l <= r:
        mid=(l+r)/2
        if nums[mid]== target:
            return mid
        if nums[mid] < target:
            l = mid+1
        else:
            r = mid-1
    return l

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]