알고리즘 - 이진 탐색(이분 탐색)

 

 

 

이진 탐색 이란 ?

 

 

• 이진 탐색(이분 탐색) 은 정렬된 데이터에서 사용하는 탐색 알고리즘이다.
• 해당 알고리즘은 탐색 탐색 범위를 반으로 계속해서 줄여나가는 방식으로 진행된다.

 

이진 탐색의 순서

 

 

 

1. 데이터 중앙에 있는 요소를 선택한다.
2. 중앙 요소의 값과 목표 값을 비교한다.
3. 목표 값이 중앙 요소의 값 보다 작으면 데이터의 왼편으로, 크다면 데이터의 오른편으로 이진 탐색을 새로 진행한다.
4. 원하는 값을 찾을때 까지 1~3의 과정을 반복한다.

 

 

 

코드 예제

 

이진 탐색의 코드는 비교적 간단하게 구현이 가능하다.

 

 static int BinarySearch(int[] array, int target)
 {
     int left = 0; // 왼쪽 끝 인덱스
     int right = array.Length - 1; // 오른쪽 끝 인덱스

     while (left <= right) // 탐색 범위의 크기가 0이 될때 까지 반복
     {
         int middle = left + (right - left) / 2; // 중앙 위치 계산

         // 타겟 값을 찾은 경우
         if (array[middle] == target)
         {
             return middle;
         }

         // 타겟 값이 중간 값보다 큰 경우, 오른쪽 부분을 탐색
         if (array[middle] < target)
         {
             left = middle + 1;
         }
         // 타겟 값이 중간 값보다 작은 경우, 왼쪽 부분을 탐색
         else
         {
             right = middle - 1;
         }
     }

     // 타겟 값을 찾지 못한 경우
     return -1;
 }

 

 

array를 받아온 다음 탐색 범위가 0이 될때까지 반복문을 돌려준다.

 

다만 중간에 원하는 값을 찾았을 경우에만 탈출 조건을 마련해 주면 된다.

 

탈출 조건은 타겟 값을 찾았거나, 탐색 범위가 0이 되었는데도 타겟 값을 찾지 못한 경우로 만들어 주었다.

 

 

 static void Main()
 {
     // 정렬된 배열
     int[] sortedArray = { 1, 3, 4, 5, 10, 20, 30, 40 };
     // 타겟 넘버
     int targetValue = 5;

     // 이진 탐색 수행
     int resultIndex = BinarySearch(sortedArray, targetValue);

     // 결과 출력
     if (resultIndex != -1)
         Console.WriteLine(resultIndex + " 번째 인덱스에 있습니다.");
     else
         Console.WriteLine("해당 원소는 배열 내에 없습니다.");
 }

 

 

 

main 문에서 배열을 원하는 대로 입력해주고 이진 탐색을 수행해보자.

 

 

 

 

 static void Main()
 {
     // 정렬된 배열
     int[] sortedArray = { 1, 3, 4, 5, 10, 20, 30, 40 };
     // 타겟 넘버
     int targetValue = 80;

     // 이진 탐색 수행
     int resultIndex = BinarySearch(sortedArray, targetValue);

     // 결과 출력
     if (resultIndex != -1)
         Console.WriteLine(resultIndex + " 번째 인덱스에 있습니다.");
     else
         Console.WriteLine("해당 원소는 배열 내에 없습니다.");
 }

 

 

 

 

 

 

 

 

 

없는 타겟 넘버를 넣어도 결과는 잘 나온다.

 

 

 

 

 

 

 

 

 

 

사진 출처 : https://www.geeksforgeeks.org/

GeeksforGeeks | A computer science portal for geeks