이진 검색(Binary Search)

검색 대상 자료가 먼저 정렬되어있어야 하며,  어떤 항목들을 두 부류로 나누어 그 가운데 조건을 만족하지 않는 부분은 버리고 최저와 최고 인덱스를 갱신하여 나머지 부분에 이분법을 반복하여 적용하면서, 원하는 검색값이 있는 항을 찾아내는 방법.

 

C언어]

void Binary_Search(int Array[],int n, int key)

{

   //int Array[] : 검색될 값들이 정렬되어있는 배열 변수

   //int n : 검색될 값들이 들어 있는 방수 변수

   //int key : 실제 검색될 값이 있는 들어있는 변수

   int low,high,mid;//이분검색을 하기위한 변수

 

   low=1;

   high=n;

 

   while(1)

   {

      mid=(low+high)/2;

      if(low>high || high<low)

      {

         printf("찾고자 하는 자료는 없습니다.\n");

         break;

      }

      if(Array[mid] == key)

      {

         printf("찾고자 하는 자료가 있습니다.\n");

         break;

      }

      else if(Array[mid] > key)

         high=mid-1;

      else

         low=mid+1;

   }

}

 

Python]

def BinarySearch(list, item):

    first = 0

    last = len(list)-1

    found = False

 

    while first <= last and not found:

        midpoint = (first + last) // 2

        if list[midpoint] == item:

            found = True

        else:

            if item < list[midpoint]:

                last = midpoint - 1

            else:

                first = midpoint + 1

    return found

 

 

 

출처]

국립 국어원 : 이진 검색

실전! 초보가 최고가 되는 C : 이진 검색(p225)

프로그래머가 알아야 할 알고리즘 40 : 이진 검색(p091)

 

 

 

참고 문제]

 

 

 

 

 

※ 10월 25일은 독도의 날입니다.

대한민국의 아름다운 영토, 독도의 겨울