Solving Skill ] 이진 탐색

이진 탐색(Binary Search)

"탐색의 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘"

 

* 탐색 범위가 큰 상황에서 탐색을 해야 할 때 사용하는 것이 좋다.

✔ 순차 탐색 (혹은 선형 검색 알고리즘)

리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나가는 알고리즘

 

- 시간 복잡도

   평균 : Θ(n)

   최악 : Θ(n)

 

- 예시( C언어 )

int sequentialSearch(int array[], int n, int m, int value) { // Starts from n to m
    int i;
    for (i = n; i <= m; i++)
        if (array[i] == value)
            return i;
    return -1;
}

 

 

** 배열 내부의 원소가 정렬이 되어있어야 사용 가능한 알고리즘입니다.

 

V 시작점, 끝점, 중간점으로 세 개의 변수를 사용하여 탐색을 합니다.

   찾으려는 데이터와 중간점 위치의 데이터를 비교하여 원하는 데이터를 찾습니다.

 

 

⏱ 시간 복잡도

     :  Θ(log n)

 

 

📑 코드 흐름(재귀 함수)

function 이진탐색(데이터, 찾는 값)

데이터가 혹시 비어 있는가?
(네) return 찾는 값 없음.

데이터의 가운데 지점을 찾는다.
찾은 지점의 값을 뽑는다.
뽑은 값이 찾는 값인가?

(네) return 뽑은 값.
(아니요)
  뽑은 값과 찾는 값을 비교한다.
  (뽑은 값이 찾는 값보다 큰 값인가?)
    return 이진탐색(데이터 앞쪽 절반, 찾는 값)
  (작은 값인가?)
    return 이진탐색(데이터 뒤쪽 절반, 찾는 값)

 

 

💻 코드 예시 (재귀)

BinarySearch(vector<int>& v, int value, int low, int high) {
    if(high < low) return -1; // not found
    
    int middle = (low + high) / 2;
    
    if(v[middle] > value) return BinarySearch(v, value, low, middle - 1);
    else if (v[middle] < value) return BinarySearch(v, value, middle + 1, high);
    else return middle; // found
}

 

 

💻 코드 예시 (반복문)

BinarySearch(vector<int>& v, int value, int low, int high) {
	while(low <= high){
    	int middle = (low + high) / 2;
        
        if(v[middle] > value) high = middle - 1;
        else if(v[middle] < value) low = middle + 1;
        // found
        else return middle;
    }
    // not found
    return -1;
}

 

 

---

 🌷 문제

    이것이 취업을 위한 코딩 테스트다

       유형 1 - 부품 찾기

       유형 2 - 떡볶이 떡 만들기

 

---

이진 탐색 - 나무위키