[리트코드/자바] 35. Search Insert Position

문제

중복되지 않는 정수로 이루어진 정렬된 배열 nums에 새로운 정수 target을 삽입하고자 한다. 정렬된 상태를 유지하면서 target이 삽입될 수 있는 index를 구하라. 만약, 배열 내에 target과 같은 값이 있다면 해당 index를 삽입 위치로 한다.

 

테스트케이스

• nums = {1, 3, 5, 6}
  target = 5
  output: 2
• nums = {1, 3, 5, 6}
  target = 2
  output: 1
• nums = {1, 3, 5, 6}
  target = 7
  output: 4

 

해설 및 풀이

1. 주어진 배열의 처음과 끝, 이를 기반으로 중앙값을 정한다.
2. 중앙값이 target보다 크다면 시작~중앙을 탐색한다
3. 중앙값이 target보다 작다면 중앙~끝을 탐색한다.

 

 

자바 구현코드

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

 

 

 

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

Search Insert Position - LeetCode