Leetcode에서 Search Insert Position 풀어보기

문제 링크

bookmark

---

이진 탐색이란

• Up & Down 게임처럼 특정 기준을 주고 up이면 그 이상에서 탐색하고 down이면 그 이하에서 탐색하는 방법
• 무조건 정렬이 된 상태에서 해야한다
• 완전 처음부터 탐색하는 배열의 O(n)과 달리 O(log n)의 시간복잡도가 소요되므로 효율성이 더 뛰어나다

---

소스 코드

function searchInsert(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;
    
    while(left <= right) {
        let mid = Math.floor((left + right) / 2);
        
        let midValue = nums[mid];
        
        if(midValue === target) return mid
        
        if(midValue < target) left = mid + 1;
        else right = mid -1;
    }
    
    return left;
};

• left와 right 의 인덱스를 초기화 해준다
• left는 0번 인덱스 right는 제일 마지막 인덱스
• 중간 인덱스에 해당하는 값과 target의 값을 계속 비교해준다
• 만약 target이 중간 인덱스 값보다 크면 왼쪽 인덱스를 +1 해준다
• 중간 인덱스보다 작으면 오른쪽 인덱스를 -1해준다
• 중간 인덱스는 왼쪽 또는 오른쪽 인덱스가 변경될때마다 다시 재할당을 해준다
• 계속 반복하다가 중간인덱스의 값과 타겟의 값이 일치하면 곧바로 그 인덱스를 리턴해준다
• 일치하지 않으면 left를 리턴해준다 ( 일치하는 값이 없을때 리턴된다 )