이진탐색(Binary Search)

💡 이진탐색(Binary Search)란?

→ 이진 탐색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.

→ 오름차순으로 정렬된 리스트의 중간 값을 임의의 값으로 선택하여 찾고자 하는 key값과 비교하는 알고리즘이다.

→ 정렬된 리스트에서만 사용할 수 있다는 단점이 존재한다.

→ 검색이 될 때마다 선형탐색(Linear Search)와는 비교할 수 없게 빨라진다.

✔️ 이진탐색 과정

1. 첫 부분과 끝부분을 가리키는 first, last, middle (= (first+last)/2) 값을 초기화
   
2. first ≤ last인지 검사
3. first ≤ last 라면, middle과 target(찾고자 하는 값)값 비교

4-1. middle == target이라면, 해당 middle을 return

4-2. middle != target이라면, middle이 target보다 큰지 비교

5-1. middle > target일 경우, last = middle-1로 변경
(target이 middle보다 작다는 정보를 얻었으므로, middle의 오른쪽 부분은 탐색할 필요x)

5-2. middle < target일 경우, first = middle+1로 변경
(target이 middle보다 크다는 정보를 얻었으므로, middle의 왼쪽 부분은 탐색할 필요x)

1. middle = (first+last)/2 값으로 변경
2. target을 찾을 때까지 위 과정 반복

✔️ 이진탐색 시간 복잡도

O(logN)

✔️ 이진탐색 구현

반복문 이용

bool BinarySearch(int *arr, int size, int target){
    int start = 0;
    int end = size-1;
    int middle;

    while(start <= end){
        middle = (start+end)/2;
        if(arr[middle] == target) return true;
        else if(target < arr[middle]){
            end = middle-1;
        }
        else{
            start = middle+1;
        }
    }
    return false;
}

References:

이진 탐색과 시간 복잡도 분석 (Binary Search and its Time Complexity Analysis)

[탐색] 이진탐색 (Binary Search) 구현 방법