[Algorithm] 이분검색(Binary Search)(c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. M = 32

    23 87 65 12 57 32 99 81 가 주어졌을 때,

    우선 주어진 수들을 정렬해준다. 편하게 std::sort 를 사용하자..

    12 23 32 57 65 81 87 99

    정렬된 배열에서 M, 32를 찾아야 한다. 

    문제가 이분검색이니까 이분검색으로 찾아야겠쥬?

    이분검색은 일렬로 나열되어있는 데이터를 정렬해서 특정 숫자를 찾는 알고리즘이라고 생각하면 되겠다.

    즉, 이분검색을 사용하기 위해서는 데이터가 정렬되어있어야 한다는 말쌈!

    

    N = 8 이다. 

    index 1 ~ 8 의 중간값을 구하기 위해 

    N을 이분하면 (1 + 8) / 2 = 4.

    index 4에 위치한 숫자는 57인데, 57은 32보다 크므로 32는 index 1 ~ 4 사이에 있다는 것을 알 수 있다.

    index 1 ~ 4 의 중간값을 구하기 위해

    이분하면 (1 + 4) / 2 = 2.

    index 2에 위치한 숫자는 23인데, 23은 32보다 작으므로 32는 index 3 ~ 4 사이에 있다는 것을 알 수 있다.

    

    index 3 ~ 4 의 중간값을 구하기 위해

    이분하면 (3 + 4) / 2 = 3

    index 3 에 위치한 숫자는 23..?! 23이므로 현재 index 를 출력하면 된다.

    여기서 구현할 때 중요한 부분은 

    start 와 end 변수를 사용하여 (start + end) / 2 = idx 가 되도록 하고

    idx 의 원소가 M 보다 작거나 클 때, start 와 end 값을 적절하게 변경해주어야 할 것이다.

  2. 

  3. 

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include <cstdio> #include <vector> #include <algorithm>   using namespace std;   int main(void) {     freopen("input.txt", "rt", stdin);       int n, m, i, start = 1, end, idx;       scanf("%d %d", &n, &m);     vector<int> vt(n + 1);          for (i = 1; i <= n; i++)         scanf("%d", &vt[i]);          sort(vt.begin(), vt.end());       end = n;       while (1)     {         idx = (start + end) / 2;           if (vt[idx] == m)         {             printf("%d\n", idx);             break;         }         else if (vt[idx] > m)             end = idx - 1;         else             start = idx + 1;     }       return 0; } Colored by Color Scripter

cs

#. Other code

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(){
    int n, i, key, lt=0, rt, mid, tmp;
 
    scanf("%d %d", &n, &key);
    vector<int> a;
    for(i=0; i<n; i++){
        scanf("%d", &tmp);
        a.push_back(tmp);    
    }
 
    sort(a.begin(), a.end());
    rt=n-1;
 
    while(lt<=rt){
        mid=(lt+rt)/2;
 
        if(a[mid]==key){
            printf("%d\n", mid+1);
 
            return 0;
        }
        else if(a[mid]>key) rt=mid-1;
        else lt=mid+1;
    }
 
    return 0;
}

while에서 나는 무한 반복으로 조건을 걸어놔서 사실 조금 위험한 코드이다.

강사님의 처럼 lt <= rt 조건을 조금만 더 생각해냈으면 좋았는데..!

rt 는 계속 감소하고 lt 는 계속 증가할테니까 언젠가 엇갈리는 순간이 올 것이다. 그 순간이 while 문이 끝나는 순간..

그래도 그 부분 말고는 강사님과 로직이 비슷해서 나름 좋다 흐흫

#. Result

  - Input --------------------------------------------------------

8 32

23 87 65 12 57 32 99 81

------------------------------------------------------------------

  - Output --------------------------------------------------------

3

------------------------------------------------------------------