[CS 지식 - 알고리즘] 이진탐색(Binary Search) & 힙정렬(Heap Sort)

1. 이진탐색(Binary Search)

• = 이진 검색
• 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘
• 장점 : 완전탐색보다 효율적이고 속도가 빠름
• 단점 : 미리 정렬이 되어있는 리스트에서만 사용가능
• 구현
  1. 초기 left, right 인덱스 값 선언
  2. left가 right보다 작거나 같다면 아래 반복
      - (left + right) / 2로 mid값 계산
      - mid값과 비교하여 찾아야하는 값으로 찾으면, 해당 값 return
      - 찾아야하는 값이 mid보다 작으면 right -1 이동
      - 찾아야 하는 값이 mid보다 크면 left +1 이동
  3. left와 right가 딱 붙어버리거나 같아지면 탐색 완료
• 예시)
  이진 탐색을 사용하여 key =32값을 찾는 과정
  1. 먼저 배열의 가운데를 결정

mid = low + (high-low) /2
    = 0 +(9-0)/2
    = 4

 

     2. 중앙 값과 검색 값을 비교

         A[4] < key 이므로 배열의 오른쪽 구간을 검색 범위로 정함

low = mid + 1
     = 4 + 1
     = 5

 

       3. 중앙 값을 결정

mid = 5+ (9-5) /2
    = 7

      4. 중앙값과 검색 값 비교
          A[7] >key 이므로 배열의 왼쪽 구간을 탐색 범위로 정함

high = mid - 1
     = 7 - 1
     = 6

        5. 중앙 값 결정

mid = 5 + (6 - 5) / 2
    = 5

        6. 중앙 값과 검색 값을 비교

            A[5] =key이므로 탐색 종료

 

• 검색종료 
  1. 검색을 성공할 경우 : 리스트에서 검색할 값과 같은 요소를 발견한 경우 
      ▶ a[mid] == key
  2.검색을 실패한 경우 : 더이상 검색할 범위가 없을 경우
     ▶low >high

검색 성공

검색실패

구현
1. 반복문을 이용한 방법

int binarySearch (int arr[], int low, int high, int key) {
  while (low <= high) {
    int mid = low + (high-low) / 2;
    
    if (arr[mid] == key) // 종료 조건1 검색 성공.
      return mid; 
    else if (arr[mid] > key) 
      high = mid - 1;      
    else 
      low = mid + 1;
  }
  return -1 ; // 종료 조건2 (low > high) 검색 실패.
}

       

     2. 재귀 함수를 이용한 방법

int binarySearch (int arr[], int low, int high, int key) {
  
  if (low > high) // 종료 조건2 검색 실패.
    return -1;  

  int mid = low + (high-low)/2;

  if (arr[mid] == key) // 종료 조건1 검색 성공.
    return mid;
  else if (arr[mid] > key)
    return binarySearch(arr, low, mid-1, key);
  else
    return binarySearch(arr, mid+1, high, key);
}

 

2. 자료구조 Heap

• 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조
  **우선순위 큐 : 가장 우순순위가 높은 데이터
• 최댓값, 최솟값을 쉽게 추출 할 수 있는 자료구조

 

 

3. 힙 정렬

• 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법
• 내림차순 정렬을 위해서는 최대힙을 구하고
  오름차순 정렬을 위해서는 최소힙을 구성하면됨
• 과정
  1. 정렬해야할 n개의 요소들로 최대 힙(완전 이진 트리형태)로 생성
      ▶ 내림 차순기준으로 정렬
  2. 한번에 한번씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장
  3. 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 됨

4. 정렬 방법

• 내림차순 정렬을 위한 최대 힙(Max Heap)의 구현
  1. heap은 1차원 배열로 쉽게 구현될 수 있음
  2. 정렬해야 할 n개의 요소들을 1차원 배열에 기억한 후 최대 힙 삽입을 통해 차례대로 삽입함
  3. 최대 힙으로 구성된 배열에서 최대값부터 삭제

1. 최대 힙의 삽입
   - 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입
   - 새로운 노드를 부모 노들과 교환해서 합의 성질을 만족시킴

 

 

 

2. 최대 힙의 삭제
   - 최대 힙에서 최댓값은 루트 노트이므로 루트 노트가 삭제
      ▶ 최대힙에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것
   - 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴
   - 힙을 재구성

[알고리즘] 힙 정렬 알고리즘 (Heap Sort) — yjglab (tistory.com)

[알고리즘] 힙 정렬 알고리즘 (Heap Sort)

[알고리즘] 힙 정렬 알고리즘 (Heap Sort)

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제 – Jihun's Development Blog (cjh5414.github.io)

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog (gmlwjd9405.github.io)

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog

[자료구조와 알고리즘] 완전탐색 / 이진탐색 (velog.io)

[자료구조와 알고리즘] 완전탐색 / 이진탐색

이진 탐색 (Binary search) 개념 및 구현 (tistory.com)

이진 탐색 (Binary search) 개념 및 구현