이분탐색/이진탐색 (Binary Search)

📍이분탐색/이진탐색 (Binary Search) 

이분 탐색 / 이진 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 

이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. 

cf) 오름차순이든 내림 차순이든 상관 없음

 

변수 3개를 사용하여 탐색하는데 보통(start, end, mid)/(low, high, mid)를 사용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진탐색의 과정이다. 

 

이진 탐색의 시간 복잡도는 O(logN)이다. 

단계마다 탐색 범위를 반으로 나누는 것과 같기 때문에 위의 시간 복잡도를 가지게 된다. 

 

 

---

💡이진탐색 알고리즘 동작 원리

위에서도 언급했지만 이진 탐색은 정렬된 상태에서만 사용가능하다. 

배열의 시작점과 끝점의 정중앙에 위치한 값을 '중앙값'이라고 부른다. 

 

만약에 탐색값이 중앙값 보다 작으면 (탐색값<중앙값) 오름차순 정렬이 되어 있기 때문에 중앙값의 오른 쪽 부분은 고려할 필요가 없다. 이런식으로 탐색 범위를 좁혀나가며 빠르게 탐색값을 찾을 수 있다. 

예를 통해 이진탐색이 어떻게 동작하는지 살펴보자. 

 

위와 같은 배열이 있고 우리는 14를 찾으려고 한다. 

 

 

1️⃣ 시작점 idx : 0 , 끝점 idx : 12, 중앙값 : 17

1). 탐색값과 중앙값 비교 

14 < 17로 탐색값이 중앙값 보다 작다. 

중앙값의 오른쪽은 볼 필요 없음. 

 

2). 시작점과 끝점을 조절하여 탐색범위를 좁힌다. 

시작점은 변동 없이 그대로 .

• 시작점 idx :0 

끝점은 중앙값의 idx보다 앞으로 이동시킨다 .

• 끝점 idx : 5

 

3). 다시 중앙값을 설정한다. 

중앙값은 시작점과 끝점 사이의 있는 인덱스의 값으로 설정한다. 

중간 인덱스가 2이므로 중앙값은 13이다. 

 

2️⃣ 시작점 idx : 0 , 끝점 idx : 12, 중앙값 : 17

1). 탐색값과 중앙값 비교 

14 >13로 탐색값이 중앙값 보다 크다. 

중앙값의 왼쪽도 볼 필요 없음. 

 

2). 시작점과 끝점을 조절하여 탐색범위를 좁힌다. 

시작점은 중앙값의 idx보다 뒤로 이동시킨다. 

• 시작점 idx : 3

끝점은 그대로.

• 끝점 idx : 5

 

3). 다시 중앙값을 설정한다. 

중앙값은 시작점과 끝점 사이의 있는 인덱스의 값으로 설정한다. 

중간 인덱스가 4이므로 중앙값은 15이다. 

 

3️⃣ 시작점 idx : 3 , 끝점 idx : 5, 중앙값 : 25

1). 탐색값과 중앙값 비교 

14 <15로 탐색값이 중앙값 보다 작다. 

중앙값의 오른쪽도 볼 필요 없음. 

 

2). 시작점과 끝점을 조절하여 탐색범위를 좁힌다. 

시작점은 그대로. 

• 시작점 idx : 3

끝점은 중앙값의 idx보다 앞으로 이동시킨다. 

• 끝점 idx : 3

 

3). 다시 중앙값을 설정한다. 

중앙값은 시작점과 끝점 사이의 있는 인덱스의 값으로 설정한다. 

중간 인덱스가 3이므로 중앙값은 14이다. 

 

 

4️⃣ 시작점 idx : 3 , 끝점 idx : 3, 중앙값 : 14

탐색값을 찾았다. 

 

 

👉 만약 탐색값이 배열에 존재하지 않는 다면,

끝점 < 시작점인 상태가 된다 . 그럼 이때 탐색을 종료하면 된다. 

 

---

💡 이진 탐색 알고리즘 구현

int binary(int num, int size){
    int start=0, end=size-1, mid=(start+end)/2;
    while(start <= end){
        if(num < input_arr[mid]){
            end = mid-1;
            mid = (start+end)/2;
        }else if(num > input_arr[mid]){
            start = mid+1;
            mid = (start+end)/2;
        }
        else if(num==input_arr[mid]){
            return 1 ; 
        }
    }
    return 0;
}

---

 

✨🎁 관련된 문제 

https://www.acmicpc.net/problem/1920

https://www.acmicpc.net/problem/10816

https://www.acmicpc.net/problem/2805

https://www.acmicpc.net/problem/2805

https://www.acmicpc.net/problem/10815

 

---