[알고리즘] Leetcode 704. Binary Search 이진 검색 알고리즘

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.

 

 

오름차순으로 주어진 정수 배열과 정수 타겟이 주어지고 타겟을 숫자로 검색하는 함수를 만드세요.

타겟이 존재한다면 index를 리턴하고 그렇지 않으면 -1를 리턴하세요. 

시간 복잡도는 반드시 O(log n)이어야 합니다.

 

---

📗 Binary Search Algorithm 이진 검색 알고리즘이란? 

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

 

1. 중간값을 선택합니다. 첫번째 값과 마지막 값을 최솟값, 최댓값으로 설정합니다.

2. 찾고자 하는 값이 중간값보다 작은지 큰지 확인합니다. 

3. 만약 크다면 중간값 이전의 값은 비교하지 않고 중간값 이후의 값만 비교합니다. 그리고 중간값이 새로운 최솟값이 됩니다.

4. 값을 찾을 때 까지 1번부터 반복합니다.

---

var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    let middle;
    let current;
    
    while (left <= right) {
        middle = Math.floor((left + right) / 2);
        current = nums[middle];

        if (current > target) {
            right = middle - 1;
        }
        
        if (current < target) {
            left = middle + 1;
        }
        
        if (current === target) {
            return middle;
        }
    }
    
    return -1; 
};

 

참고 및 출처

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98