[알고리즘] 최대값/최소값 찾기 in 정렬된상태

최대값/최소값은 간단하다.

기본틀은 분할 정복을 기반으로 하며 간단하게 구현된다.

. 오름차순 : 최대값 (오른쪽으로 이동한다. 커지는 방향이다. 멈춘곳이 최대이다.)

. 내림차순 : 최소값 (왼쪽으로 이동한다. 작아지는 방향이다. 멈추면 최소인위치이다.)

최대값 찾기

정렬된 주어진

#include<stdio.h>

int buffer[] = { 1, 3, 5, 7, 9, 11 };

int getMax(int target)
{
    int keep = 0;

    int s = 0;
    int e = 5;

    int m = (s + e) / 2;

    while (s <= e)
    {
        if (buffer[m] <= target) // 요기
        {
            s = m + 1;
            keep = m;   // 요기가 주요하다.
        }
        else
        {
            e = m - 1;
        }

        m = (s + e) / 2;
    }

    return keep;
}


int main(void)
{

    printf("1 == %d\n", buffer[getMax(2)]);
    printf("3 == %d\n", buffer[getMax(4)]);
    printf("5 == %d\n", buffer[getMax(6)]);
    printf("7 == %d\n", buffer[getMax(8)]);
    printf("9 == %d\n", buffer[getMax(10)]);


    return 0;
}

최소값 찾기

#include<stdio.h>


int buffer[] = { 1, 3, 5, 7, 9, 11 };



int getMax(int target)
{
    int keep = 0;

    int s = 0;
    int e = 5;

    int m = (s + e) / 2;

    while (s <= e)
    {
        if (buffer[m] <= target)
        {
            s = m + 1;
            keep = m;
        }
        else
        {
            e = m - 1;
        }

        m = (s + e) / 2;
    }

    return keep;
}

int getMin(int target)
{
    int keep = 0;

    int s = 0;
    int e = 5;

    int m = (s + e) / 2;

    while (s <= e)
    {
        if (buffer[m] < target) // 요기 핵심
        {
            s = m + 1;
        }
        else
        {
            e = m - 1;
            keep = m;  // 요기 핵심
        }

        m = (s + e) / 2;
    }

    return keep;
}



int main(void)
{

    printf("3 == %d\n", buffer[getMin(2)]);
    printf("5 == %d\n", buffer[getMin(4)]);
    printf("7 == %d\n", buffer[getMin(6)]);
    printf("9 == %d\n", buffer[getMin(8)]);
    printf("11 == %d\n", buffer[getMin(10)]);


    return 0;
}