[Java/Python3] leetcode 35. Search Insert Position

문제

https://leetcode.com/problems/search-insert-position/description/

Search Insert Position - LeetCode

이진 탐색을 할줄 아니? 물어보는 문제

 

풀이

정렬된 배열에서의 이진 탐색 알고리즘은 다음과 같다.  자주 사용되는 O ( lon N ) 로직임으로, 아직 모른다면 꼭 공부 해야한다.

1. left = 0 , right = nums.length -1 로 양 끝단 위치를 가리키는 포인터를 생성한다.
2. left 와 right 의 절반 지점에 있는 mid 포인터를 생성.
3. mid < target 이면, [ left .. mid ] 범위 안에는 target이 존재하지 않음으로, left = mid + 1
4. mid > target 이면, [mid .. right] 범위 안에 target이 존재하지 않음으로 날린다 .
5. mid == target이면 return mid
6. 그게 아니면 , left 를 리턴한다.

코드

자바

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1; 
        int mid = left + (right - left)/2;
        while(left <=right){
            mid = left + (right - left)/2;
            
            if(nums[mid] == target)return mid;
            else if(nums[mid] < target) left = mid+1;
            else right = mid-1;
        }
        return left;
    }
}

 

파이썬

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