[알고리즘] Binary Search

치치·2025년 1월 16일

알고리즘

알고리즘C++

목록 보기

6/24

이진 탐색

탐색 범위를 반으로 나누어서 찾는 값을 포함하는 범위를 좁혀나가는 방식의 알고리즘이다
주로 오름차순으로 정렬되어 있는 상태에서 사용해야한다

맨 처음 배열에서 left값은 [0]를, right값은 [SIZE -1] 을 가리킨다
pivot은 (left + right) / 2;를 가리킨다
-> 연산자 우선순위 까먹지 말자!!

1. 반복문을 사용

#include <iostream>
#define SIZE 8
using namespace std;

void BinarySearch(int list[], int key)
{
	int left = 0;
	int right = SIZE - 1;

	while (left <= right)
	{
		int pivot = (left + right) / 2;

		if (key == list[pivot])
		{
			cout << "Key Found : " << list[pivot];
			return;
		}
		else if (key > list[pivot])
		{
			left = pivot + 1;
		}
		else if (key < list[pivot])
		{
			right = pivot - 1;
		}
	}
	cout << "Not Key Found" << endl;
}

// 재귀사용방식

int main()
{
#pragma region 이진 탐색

	// right < left면 값을 못찾은 상태 (엇갈림)

	int list[SIZE] = { 1,2,30, 42,50, 55, 60,70 };

	BinarySearch(list, 30);

#pragma endregion



	return 0;
}

반복문의 조건이 while (left <= right) 인 이유

만약 내가 원하는 key값을 이 조건이 종료될 때까지 발견 못할 경우를 예로 들어보자

위와 같은 배열에서 찾고자 하는 key값을 65로 설정
pivot과 key값을 비교하며 left와 right의 위치를 이동
left와 right의 위치가 같아졌고 pivot의 위치도 같아졌을때, right와 left가 엇갈리는 경우가 있다
-> 이 경우는 key값이 없기때문
현재 경우는 pivot이 key값보다 작은 경우이고, 반대로 pivot이 key값보다 큰 경우는 오른쪽 범위에서 비슷하게 작동한다

이진탐색 다시 해보기

다시 코드를 짰을때, 실행에 제대로 안된다.
-> 이유는 pivot 변수의 위치였다..!!!

#include <iostream>
using namespace std;
#define SIZE 8

// 이진탐색
// 배열의 크기는 8 
// 오름차순 정렬로 되어있는 상태로 탐색
// 
// 매개변수로 배열과 찾고자 하는 key값을 받는다

// 1. 반복문 사용방식
void BinarySearch(int list[], int key)
{
    int left = 0;
    int right = SIZE - 1;
    

    while (left <= right)
    {
        int pivot = (left + right) / 2;
        // 키 찾으면 바로 종료
        if (key == list[pivot])
        {
            cout << "Key Found : " << list[pivot] << endl;
            return;
        }
        else if (key > list[pivot])
        {
            left = pivot + 1;
        }
        else if (key < list[pivot])
        {
            right = pivot - 1;
        }
    }
    // 반복문이 종료되어도 찾지 못했으면 찾는key값이 없는 것
    cout << "Not Key Found" << endl;
}


int main()
{
    int list[SIZE] = { 1,2,30, 42,50, 55, 60,70 };
    BinarySearch(list, 30);

    return 0;
}

pivot의 위치값은 이진탐색을 하면서 배열의 범위가 반씩 줄어들때마다 pivot값도 계속 바뀌기 때문에 반복문 안에 선언해주어야함

이진탐색 재귀로 구현해보기

재귀로 구현할 경우, 함수를 빠져나갈 수 있는 조건을 가장 위에 설정해두어야 한다
기존 반복문을 사용하던 방식과 동일하게 left가 right보다 커지는 경우(엇갈림)가 발생하면 함수를 종료한다

#include <iostream>
using namespace std;
#define SIZE 8

// 이진탐색
// 배열의 크기는 8 
// 오름차순 정렬로 되어있는 상태로 탐색
// 
// 매개변수로 배열과 찾고자 하는 key값을 받는다

// 2. 재귀 사용방식
void BinarySearch(int list[], int key, int left, int right)
{
    // 함수 종료
    if (left > right)
    {
        // 찾는key값이 없는 것
        cout << "Not Key Found" << endl;
        return;
    }

    int pivot = (left + right) / 2;

    // 키 찾으면 바로 종료
    if (key == list[pivot])
    {
        cout << "Key Found : " << list[pivot] << endl;
        return;
    }
    else if (key > list[pivot])
    {
        left = pivot + 1;
        BinarySearch(list, key, left, right);
    }
    else if (key < list[pivot])
    {
        right = pivot - 1;
        BinarySearch(list, key, left, right);
    }
}
int main()
{
    int list[SIZE] = { 1,2,30, 42,50, 55, 60,70 };

    int left = 0;
    int right = SIZE - 1;

    BinarySearch(list, 30, left, right);

    return 0;
}