[Binary Search] 수 찾기 - 백준 1920번

1920번: 수 찾기

• binary search 했는데도 까먹는 나…
• 104ms가 내가 한 방식… 그 위에가 binary search로 푸는 방식,, 그냥 binary search 쓰자..

내가 한 방식

• O(n^2) 절대 안됨 10^5 * 10^5 = 10^10 = 100억
  1. 둘 다 Sorting
  2. 두 vector를 나란히 진행하면서 크기 비교
  1. 숫자가 작은 쪽을 한칸 뒤로
  2. 같으면 vec3 에 저장 (누가 겹치는지 (1 3 5))
     1. 겹치는 숫자의 index 검색 (sorting 때문에 엉켜벌임)
  3. 숫자가 중복 될 수 있기 때문에 map<int, vector<int> > 사용
     1. index를 찾았으면 0으로 초기화한 vector의 index의 value를 1로 변경

Binary Search로 풀기

무조건 Sorting 필요함!!

1. sorting
2. 숫자 하나하나 binary_search 돌려준다.

if(binary_search(vec.begin(), vec.end(), number)){
		cout << "1\n";
} else {
		cout << "0\n";
}

개쉽다.

• binary_search가 기억 안날경우

int binary_search(int begin, int end, int target) {
    if (begin >= end) return 0;
    int mid = (end - begin) / 2 + begin;
    if (target == a[mid]) return 1;
    else if (target > a[mid]) return binary_search(mid + 1, end, target);
    else return binary_search(begin, mid, target);
}