[자료구조] 09 이진탐색

이진탐색이 생각보다 굉장히 중요하다고 들었다

자료구조의 초반에 나오지만 어쩌면 기본 중에 기본이고 기업 코딩 테스트에서들도 이를 기반으로 한 테스트들이 나온다고 하던데 🤔

 

 

✔️ 순차 탐색 알고리즘 (sequential search) 

어떤 항목을 찾기위해서 가장 단순하게 탐색하는 알고리즘

원하는 항목을 찾을 때까지 순차적으로 다음 항목과 반복해서 비교하는 방법 

 

장점 👉 항목들이 정렬될 필요없이 바로 적용 가능

단점 👉 탐색 성능 편차가 심함 (정렬이 되어 있을 때랑 안 되어 있을 때)

평균 비교 횟수 👉 n/2 

 

 

 

✔️ 이진탐색이란  (Binary Search)

정렬된 데이터들에서 중간값(median)과 크기를 비교하고,

그 결과에 따라서 발견이 될 것 같은 가능성이 있는 리스트에서만 이 과정을 반복하는 탐색 알고리즘 

 

장점 👉 한번 비교할 때마다 탐색 대상이 절반으로 감소

단점 👉 정렬된 항목 리스트에만 적용이 가능

비교 횟수 👉 n개의 원소일 때 이진 탐색  => log2N (밑이 2) 번의 비교 횟수만 요구함 => 순차 탐색보다 빠르다 

 

 

📌 Binary Search 

1. 정렬된 항목 리스트에 대해 중간값 (median) 과 키 값(search key) 비교

2. 탐색 키가 중간 값과 같다? => 종료

3. 탐색 키가 중간 값보다 크다? => 오른쪽에 내가 찾는 항목이 있을 것이다! 오른쪽 서브 리스트에 대해서 반복

탐색 키가 중간 값보다 작다? => 왼쪽에 내가 찾는 항목이 있을 것이다! 왼쪽 서브 리스트에 대해서 반복

4. 모든 수와 비교하였는데 탐색 키를 찾지 못했다? => 종료

 

#include <stdio.h>
int binary_search(int list[], int item, int left, int right);


void main()
{
    int pos, max = 12, item = 60;
    int mine = {4,7,12,18,32,36,48,53,60,67,80,82};
    pos = binary_search(mine, item, 0, max-1);

    printf("where? : %d", pos);
}

int binary_search(int list[], int item, int left, int right){
    int median;
    while(left <= right){
        median = (left + right)/2;
        if(list[median] == item){
            return median;
        }
        else {
            if(item < list[median]){ //왼쪽 서브 트리를 봐야한다
                right = median - 1;
            }else{
                left = median + 1;
            }
        }
        return -1;
    }
}

//재귀적 방법 이용한 이진 탐색
int rbinary_search(int list[], int searchkey, int left, int right){
    int median;
        if(left <= right){
            median = (left + right)/2;
            if(searchkey < list[median]){ //왼쪽 서브 트리를 봐야한다
                return rbinary_search(list, searchkey, left, median-1);
            }
            else if(searchkey > list[median]){ //오른쪽 서브 트리를 봐야한다
                return binary_search(list, searchkey, median+1, right);
            }
            else{
                return median;
            }
        }
        return -1;
}

 

💢 아래 오류 나옴 ❗️

Segmentation Fault

//고민좀 해보자..