Skip to content

Latest commit

 

History

History

binary_search

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
src
src
 
 
README.md
README.md
 
 

README.md

Binary Search

이분 탐색

  • 정렬되어 있는 배열에서 특정 요소를 찾기 위해 모든 데이터를 순차적으로 탐색하는 것(선형탐색)이 아닌 탐색 범위를 절반으로 줄여가며 탐색하는 방법(이분탐색)
  • 선형탐색의 시간복잡도는 O(n)
  • 이분탐색의 시간복잡도는 O(log n)

이분 탐색 소스코드 (C)

#include <string.h>
#include "key.h"

/* binsearch: find word in tab[0]...tab[n-1] */
struct key *binsearch(char *word, struct key tab[], int n)
{
    int cond;
    struct key *low  = &tab[0];
    struct key *high = &tab[n];
    struct key *mid;

    while (low < high) {
        mid = low + (high - low) / 2; /* `mid = (low + high) / 2` is WRONG! */
        if ((cond = strcmp(word, mid->word)) < 0)
            high=mid;
        else if (cond>0)
            low = mid + 1;
        else
            return mid;
    }

    return NULL;
}

연습문제

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> v(n);
  for (int i = 0; i < n; ++i)
    std::cin >> v[i];
  std::sort(v.begin(), v.end());

  int m;
  std::cin >> m;
  while (m--) {
    int target;
    std::cin >> target;

    auto low = v.begin();
    auto high = v.end();
    while (low < high) {
      auto mid = low + (high - low) / 2;
      if (target < *mid)
        high = mid;
      else if (target > *mid)
        low = mid + 1;
      else
        break;
    }
    std::cout << ((low < high) ? 1 : 0) << '\n';
  }

  return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> v(n);
  for (int i = 0; i < n; ++i)
    std::cin >> v[i];
  std::sort(v.begin(), v.end());

  int m;
  std::cin >> m;
  while (m--) {
    int target;
    std::cin >> target;
    std::cout << binary_search(v.begin(), v.end(), target) << '\n';
  }

  return 0;
}

lower_bound

  • Returns an iterator pointing to the first element which does not compare less than val.
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, 
                            ForwardIterator last, 
                            const T& val)
{
    ForwardIterator it;
    iterator_traits<ForwardIterator>::difference_type count, step;

    count=distance(first,last);
    while (count>0) {
        it=first; 
        step=count/2; 
        advance(it,step);
        if (*it<val) {
            first=++it;
            count-=step+1;
        }
        else {
            count=step;
        }
    }

    return first;
}

upper_bound

  • Returns an iterator pointing to the first element which compares greater than val.
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, 
                            ForwardIterator last, 
                            const T& val)
{
    ForwardIterator it;
    iterator_traits<ForwardIterator>::difference_type count, step;

    count=distance(first,last);
    while (count>0) {
        it=first; 
        step=count/2; 
        advance(it,step);
        if (!(val<*it)) {
            first=++it;
            count-=step+1;
        }
        else {
            count=step;
        }
    }

    return first;
}

lower_bound, upper_bound 예시

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
  std::vector<int> data = {1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6};

  auto lower = std::lower_bound(data.begin(), data.end(), 4);
  auto upper = std::upper_bound(data.begin(), data.end(), 5);

  // result: 4 4 4 5 5 
  // idx :  0  1  2  3  4  5  6  7  8  9 10 11 12
  // data:  1  1  2  3  3  3  3  4  4  4  5  5  6
  // lower_bound: the lower will indicate to the idx 7
  //              the first element which does not compare less than 4
  // upper_bound: the upper will indicate to the idx 12
  //              the first element which compares greater than 5
  std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
  return 0;
}

연습문제

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> v(n);
  for (int i = 0; i < n; ++i)
    std::cin >> v[i];
  std::sort(v.begin(), v.end());

  int m;
  std::cin >> m;
  while (m--) {
    int t;
    std::cin >> t;
    auto upper = std::upper_bound(v.begin(), v.end(), t);
    auto lower = std::lower_bound(v.begin(), v.end(), t);
    std::cout << upper - lower << ' ';
  }

  return 0;
}

Parametric Search

  • 이분 탐색 응용
  • 최적화 문제, 이를테면 주어진 조건을 만족하는 값 중에서 최소 혹은 최대값을 구하는 문제를 결정 문제로 바꾸어 푸는 것
    • 이분 탐색을 사용해 탐색 범위를 줄여놓고, 주어진 조건에 만족하는 결과를 찾는 것
    • 조건을 만족할 경우에만 값을 기록

연습문제

/*
  Copyright 2022 Ryan M. Jeong <[email protected]>
*/

// CP
#define CP do {                     \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(NULL);               \
} while (0)

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  CP;

  // 최적화 문제: 랜선 n개를 만들 때 각 랜선의 최대 길이
  // 결정 문제: 각 랜선의 길이가 x일 때, 랜선이 n개 이상인가? (최대)
  int k, n;
  std::cin >> k >> n;
  std::vector<int> v(k);
  for (int i = 0; i < k; ++i)
    std::cin >> v[i];
  std::sort(v.begin(), v.end());

  int res = 0;
  int64_t low = 1;
  int64_t high = static_cast<int64_t>(v.back()) + 1;  // [low, high)
  while (low < high) {
    int64_t mid = (low + high) / 2;
    int cnt = 0;
    for (const int& l : v)
      cnt += l / mid;

    if (cnt >= n) {
      low = mid + 1;
      res = mid;
    } else {
      high = mid;
    }
  }
  std::cout << res;

  return 0;
}
이전 - Sort 목록 다음 - Two Pointer