Binary Search   이진 검색, 이진 탐색

(2019-09-23)
1. 이진 탐색 (Binary Search)                              

  ㅇ 실행 방식
     - 기 정렬되어있는 순서 리스트에서 만 가능한 검색 방법
     - 중앙 위치로부터 탐색 범위를 반씩 줄이면서 자료를 찾는 방법   ☞ 분할 정복법 참조

  ㅇ 시간복잡도 : O(log n)

  ㅇ 적용 : 정렬된 자료 만 가능

  ㅇ 알고리즘 표현
      
Input  : int n, array Data[1,...,n], key x
Output : int location (검색 실패시 0)

void binary_search (int n, array Data[], key x, int &location) {
   int low=1, high=n, mid ;
   location = 0 ;
   while (low <= high and location == 0) {
      mid = (low + high)/2 ;
      if (x == Data[mid])
         location = mid ;
      else if (x < Data[mid])
         high = mid - 1 ;
      else 
         low = mid + 1;
   }
}
- ① 먼저 상한(high),하한(low)을 정함 - ② 최초 하한은 배열의 첫째값, 상한은 배열의 끝값 - ③ 상한,하한 사이에 중간값을 찾는 루프 . ⓐ 중간값 지정 (상한,하한의 가운데) . ⓑ 찾던 값이 중간값 보다 큰지 작은지에 따라, 하한 또는 상한을 재지정 . ⓒ 찾던 값이 중간값 이면, 검색 끝냄 - ④ 상한,하한 구간을 줄여가는 중에 역전되면, 이 배열에 찾는 값이 없는 것임 ㅇ ... (작성중) ...


[검색 알고리즘] 1. 검색 알고리즘 2. 선형 검색 3. 이진 검색 4. 해싱 탐색 5. 해쉬 생성

 
        최근수정     요약목록     참고문헌