순차탐색과 이진탐색 알고리즘에 대해 알아보자!

1. 순차탐색(Sequential Search)

• 찾고자 하는 값과 배열의 원소를 순서대로 비교해서 찾으면 해당 인덱스를 반환, 값이 없다면 -1 또는 null을 반환합니다.
  
  
• 시간복잡도 = O(n)번

<이미지 출처: https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcuQicy%2FbtqHMwvIWGK%2F7rPy5JIYmOuI7vb78dWHF0%2Fimg.png>

 public int SequentialSearch(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;
            }
        }

        return -1;
    }

 

---

2, 이진탐색(Binary Search)

• 배열을 크기 순으로 정렬합니다.
  
  
• 정렬된 배열에서 정중앙에 위치한 값을 찾습니다.
• 찾고자 하는 값을 정중앙의 값과 비교해서 다음에 비교할 구간을 찾습니다.
• 위 과정을 반복하여 찾고자하는 값이 있다면 해당 인덱스를 반환, 없다면 -1 또는 null을 반환합니다.
  
  
• 시간복잡도 = log2(n)번

<이미지 출처: https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FA19rE%2FbtqHxc0yaka%2FPOTMTtkKYZSzudXVyDUOUK%2Fimg.png>

public int BinarySearch(int data, List<int> list)
    {
        if (list.Count == 0) return -1;

        list.Sort();

        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;
    }

---