fork download 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. // arr은 오름차순 정렬되어있고, 같은 값을 가진 원소가 없다고  가정
  8. // n이 존재하지 않는 경우는 없다고 가정
  9. int bs(vector<int> arr, int n) {
  10.     // 시간 복잡도 테스트용 카운터
  11.     int count = 0;
  12.     const int length = arr.size();
  13.     int delta = length / 4;
  14.     int index = length / 2;
  15.     while(arr[index] != n) {
  16.         count++;
  17.         if(arr[index] < n) {
  18.             index += delta;
  19.             if(delta < 1) {
  20.                 index++;
  21.             }
  22.         } else {
  23.             index -= delta;
  24.             if(delta < 1) {
  25.                 index--;
  26.             }
  27.         }
  28.         delta /= 2;
  29.     }
  30.     cout << "size: " << length << endl;
  31.     cout << "count: " << count << endl;
  32.     return index;
  33. }
  34.  
  35. int main() {
  36. 	vector<int> arr;
  37.     // 테스트 배열 초기화
  38.     for(int i=0;i<1000000;i++) {
  39.         arr.push_back(i + 1);
  40.     }
  41.     cout << "location is: " << bs(arr, 3) << endl;
  42. 	return 0;
  43. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
Standard input is empty
stdout 
size: 1000000
count: 23
location is: 2
https://ideone.com/pbBBMU
이탐
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!