Merge / Quick Sort & Binary Search

Merge sort

 

Sorting 방법 중 하나.

 

배열을 반으로 쪼개어(divide), 더 이상 나눌 수 없을 때 다시 합치면서(conquer) 배열을 정렬한다.

 

Complexity: O(n log n) 으로 안정적이다.

 

 

Quick sort

 

Sorting 방법 중 하나.

 

하나의 pivot을 잡아 왼쪽에 pivot보다 작은 수들을, 오른쪽에 pivot보다 큰 수들을 놓은 다음,

 

좌, 우로 나누어 다시 pivot을 잡고 위의 과정을 진행한다.

 

Complexity: O(n log n), O(n^2) (worst case)

 

 

Binary search

 

정렬되어 있는 배열에서 원하는 원소를 O(log n)만에 찾는 방법.

 

int binary_search(int num[], int from, int to, int target) {

  while (from <= to) {
    int mid = (from + to) / 2;
    
    if (num[mid] < target) {
      from = mid + 1;
    } else if (target < num[mid]) {
      to = mid - 1;
    } else {
      return mid;
    }
    
  return -1;
}

 

lower_bound, upper_bound도 binary search를 통해 쉽게 구현할 수 있다.