사전에서 단어 찾는 방법 : 이진 탐색(Binary Search)

* 2022년 10월 18일 velog에 작성했던 게시글을 옮겨온 글입니다.

 

 

사전순으로 정렬이라는 말은 A, B, C.. 혹은 ㄱ, ㄴ, ㄷ 순으로 앞에서 뒤로 작은 것부터 큰 것까지 차례대로 늘어놓은 것을 말한다. 만약 이렇게 정렬된 사전에서 특정 단어를 찾으라고 한다면 우리는 자연스럽게 이진 탐색 방법을 이용할 것이다. 우리도 모르게 사용하고 있는 이진 탐색 알고리즘은 정렬이 되었다고 약속되었을 때 효율적이다.

 

만약 Canada라는 단어를 찾는다면 우리는 사전 한 가운데를 펼치고 그 페이지에 나오는 단어들의 시작이 C보다 앞인지 뒤인지를 판단한다. 만약 뒤라면 그 뒷 페이지는 더이상 볼 필요가 없어진다. 다시 남은 절반의 페이지들의 가운데를 펼쳐 앞의 과정을 반복하다 보면 단 몇번만에 찾을 수 있다. 앞에서부터 차례대로 찾는 것보다 훨씬 적은 반복을 요구하며 그 횟수가 계산될 수 있다.

 

📈 시간 복잡도

선형 탐색 O(N)
이진 탐색 O(logN)

 

 

둘의 시간 복잡도를 비교하면 이진 탐색이 효율적인 탐색 방법이라는 것을 알 수 있다. 단, 앞에서 언급한 것처럼 이진 탐색은 정렬이 되었다는 가정하에 사용할 수 있다. 그렇지 않고 무작위로 나열되었다면 선형 탐색 방법을 쓸 수 밖에 없다.

 

문제

 

[LeetCode] 704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

 

예시

 

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

 

제한 조건

 

Constraints:

• 1 <= nums.length <= 104
• -104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

나의 풀이

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0
    let right = nums.length - 1

    while(left <= right) {
        let mid = Math.floor((left + right) / 2)
        if (target === nums[mid]) {
            return mid
        } else if (target > nums[mid]) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
};

1. 우선 정렬이 되어있지 않다면 정렬해야 하지만 해당 문제에선 이미 정렬이 되어있다.
2. 왼쪽, 오른쪽, 가운데 index를 지정해야 하므로 재할당이 가능한 let으로 선언해준다.
3. 왼쪽 index가 오른쪽 index보다 작거나 같을 때까지 반복되며 가운데 index는 양 끝 index를 더해서 2로 나누고 반올림 해준 값이다.
4. 만약 찾는 대상이 가운데 index와 일치하다면 반환한다.
5. 그렇지 않고 찾는 대상이 가운데 index보다 크다면 왼쪽 index를 가운데 index+1로 옮긴 후 4번을 반복 한다.
6. 반대라면 오른쪽 index를 가운데 index-1로 옮긴 후 4번을 반복 한다.
7. 만약 끝까지 수행해도 만족하지 못한다면 -1을 반환한다.