Algorithm: Binary Search

Binary Search 란 정렬된 배열에서 원하는 값을 빠르게 찾기 위한 알고리즘이다

Binary Search는 반으로 나누어 검색하는 방법으로 시간 복잡도는 O(log n) 이다. 

 

동작과정

1. 배열의 중간값을 선택한다

2. 중간값과 찾고자 하는 값을 비교

    --> 중간값이 찾고자 하는 값과 같으면 검색을 종료

    --> 찾고자 하는 값이 중간값보다 작으면 배열의 왼쪽으로 다시검색

    --> 찾고자 하는 값이 중간값보다 크다면 배열의 오른쪽으로 다시 검색

    --> 위 방법 반복

 

경비실 문제

 

무식한 방법

    M이 가장 왼쪽에 있는 집부터 가장 오른쪽에 있는 집까지의 거리.

    모든 (M,k) 에 대해 다 조합해본다: O(M^k) 시간

 

    착안점

        --> 경비실이 k개 있다면 집에서 경비실 까지의 거리는 M/(2k) 보다 멀 수 없다.

        --> 경비실을 하나 더 놓는다면 최대 거리는 확실히 줄어든다

 

다른 방법(이진 탐색)

        --> 집들을 x 좌표 기준으로 정렬

        --> 맨 왼쪽 집부터 오른쪽까지 읽어나가며, k개의 경비실을 놓아서 가장 먼 집까지의 거리가 d가 되는지 점검.

        --> 맨 왼쪽 집을 생각해보자

                --> 경비실은 이 집의 좌표에서 d 만큼 오른쪽에 떨어진 곳에 있을 것.

                --> 이 경비실로부터 거리가 d 이내인 집을 모두 제거한 다음, 남은 집에 대해 똑같은 과정을 반목하면 필요한 경                         비실의 수

        --> 만약 필요한 경비실의 수가 k 이하라면, d 값을 줄여서 답이 되는지 점검

        --> 만약 필요한 경비실의 수가 k 초과라면, d 값을 더 키워야 한다

 

Heron's Method

• sqrt(2) 의 값은?
  • 1은 확실히 아니다. 2도 아니다.
  • 그렇다면 (1+2/1)/2 = 3/2 도 답이 아니지만 위보다 근접
  • 그렇다면, (3/2+2/(3/2))/2 = 17/12 는 위보다도 더 근접
  • x < sqrt(2) 라면 2/x > sqrt(2) 이므로 (x + 2/x) / 2 는 x, 2/x 보다 훨씬 sqrt(2) 에 가깝다