🤍 알고리즘 - 이분탐색이 무엇이고 시간복잡도는 어떻게 되며 그 이유는 무엇인가요

8) 알고리즘 - 이분탐색이 무엇이고 시간복잡도는 어떻게 되며 그 이유는 무엇인가요?

• 이분탐색이란 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘이다.

• 배열의 중간을 기준으로 탐색하기 때문에 반드시 데이터가 정렬된 상태로 존재해야 하며 시간 복잡도는 O(log n) 으로 배열을 전수 조사하는 O(n)에 비해 상대적으로 빠른 탐색 알고리즘이다.

• 여기서 O(log n) 만에 값을 찾을 수 있는 이유는 중간을 기준으로 탐색 대상을 절반씩 줄여나가기 때문이다.

  

  • 이진 검색을 하려면 우선 가운데 값을 찾아서 key값(지금 구하려는 수)과 비교를 한다.

  • 2<7이므로 뒷 부분은 버리고 앞 부분만 탐색한다.

  • 가운데 값이 3을 가지고 비교한다. 2<3 이므로 앞 부분만 다시 탐색한다.

  • 2>1 이므로 다시 탐색하고 더 이상 남은 항목이 없으므로 탐색 실패.

  • 이렇게 한 번 처리가 진행될 때마다 검색해야 하는 데이터의 양이 절반씩 뚝 뚝 떨어지는 것을 O(log n) 알고리즘이라고 한다.

    public int F(int k, int[] arr, int s, int e) {
        if (s > e) {
            return -1;
        }
      
        int m = (s + e) / 2;
      
        if (arr[m] == k) {
            return m;
        } else if (arr[m] > k) {
            return F(k, arr, s, m - 1);
        } else {
            return F(k, arr, m + 1, e);
        }
    }
  
  

  • 처음 호출 될 때는 시작 부분은 0, 끝 점은 배열의 맨 마지막 방이 된다.

  • int m = (s + e) / 2; 주어진 range에 중간값을 찾는다.

  • 찾는 값이 중간 값보다 작으면 중간 지점 바로 전 까지 range를 조정해서 다시 호출하고 중간 값보다 크면 중간 지점 다음 방부터 range를 조정해서 다시 호출한다.

  • 이렇게 하면 한 번 함수가 호출될 때마다 중값값을 기준으로 절반은 검색 영역에서 제외시켜 버리기 때문에 순차 검색에 비교해서 속도가 현저하게 빠르다.