LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 정렬된, 중복 숫자가 없는 배열 nums, 타겟 값 target
2. output: nums에서 target의 idx, 혹은 target이 정렬되어야 하는 idx 리턴
3. 시간 복잡도 O(log n) 제한
   • 1 <= nums.length <= 104
   • 104 <= nums[i] <= 104
   • nums contains distinct values sorted in ascending order.
   • 104 <= target <= 104

Idea

이미 정렬되어 있는 배열에서 log n 안에 탐색 → 이분 탐색

Solution

1. 이분탐색

   정확히 target값이 nums에 없는 경우, 삽입 위치를 리턴해야 하므로 양 끝에 오는 경우만 처리해주면 됨

   class Solution {
       fun searchInsert(nums: IntArray, target: Int): Int {
           if (nums.size == 1) return if (nums[0] < target) 1 else 0
           if (target <= nums.first()) return 0
           if (target > nums.last()) return nums.size
           var start = 0
           var end = nums.size - 1
           var mid = (start + end) / 2
           while (start + 1 != end) {
               if (nums[mid] == target) return mid
               if (nums[mid] < target) {
                   start = mid
               } else {
                   end = mid
               }
               mid = (start + end) / 2
           }
           return start + 1
       }
   }
   

   시간 복잡도: 문자열 이분탐색 = log n

   

Point