[알고리즘] 탐색 알고리즘(feat. 순차탐색, 이진탐색)

---

1. 순차 탐색 (Sequential Search)

데이터들을 하나씩 비교해서 원하는 데이터를 찾는 방법입니다.

public int searchIndex(int data, List<int> list)
{
    if (list.Count == 0) return -1;
    for (int i = 0; i < list.Count; i++)
    {
        if (list[i] == data) //원하는 데이터를 찾음
            return i; //단, 같은 데이터가 여러개 있어도 제일 앞에 있는 데이터의 index 리턴
    }
    return -1; //원하는 데이터가 없을 경우
}

 

---

2. 이진 탐색(Binary Search)

데이터를 둘로 나누고, 둘 중 원하는 데이터가 있을만한 곳을 찾는 방법입니다.

순차 탐색과는 다르게 데이터들이 이미 정렬을 마친 상태여야 합니다.

public int searchIndex(int data, List<int> list)
{
    if (list.Count == 0) return -1;
    int startIndex = 0;
    int endIndex = list.Count - 1;
    while(true)
    {
        int midIndex = (startIndex + endIndex) / 2;
        if (list[midIndex] == data) return midIndex;
        else if (list[midIndex] > data) endIndex = midIndex - 1;
        else startIndex = midIndex + 1;
        if (startIndex == endIndex)
        {
            if (list[endIndex] == data) return endIndex;
            break;
        }
    }
    return -1; //원하는 데이터가 없을 경우
}