배열에서 삽입 위치 찾기 (쓰면서 익히는 알고리즘 자료구조)

1.5 배열에서 삽입위치 찾기

• 문제링크  : https://leetcode.com/problems/search-insert-position/

📌 Problem

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.

Example 1:

Input: nums = [1,3,5,6], target = 5 Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2 Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7 Output: 4

Example 4:

Input: nums = [1,3,5,6], target = 0 Output: 0

Example 5:

Input: nums = [1], target = 0 Output: 0

 

Constraints:

• 1 <= nums.length <= 104
• −104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• −104 <= target <= 104

📝 Solution

 

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

• Time complexity : O(logn)
• 배열 요소를 BinarySearch 으로 접근
• 요소를 찾는다면 해당 인덱스 반환한다.
• 끝까지 찾지 못하고 이진탐색을 종료한다면 최종 접근했던 낮은 인덱스의 값을 반환한다.

 

이진탐색(BinarySearch)

이진탐색은 한번 비교를 거칠때 탐색 범위가 반(1/2)으로 출어들기 때문에 탐색 속도가 매우 빠르다.

정렬된 배열을 전제로 한다.

이진 탐색을 사용할때는 배열이 정렬되 있는 상태거나 배열 정렬 시 발생되는 소요시간이 많지 않은 상황에서 사용하는 것이 좋다.