[알고리즘]이진검색(이분탐색)이란(Binary Search)

▷ 목표

• 이진검색 알고리즘을 이해합니다.
• 이진검색을 이용하여 배열의 특정 원소의 위치를 찾을 수 있습니다.
• 이진검색 알고리즘의 특징
• 이진검색 알고리즘의 시간복잡도를 이해합니다.

▷ 이진검색의 개념

탐색 범위를 두 부분으로 분할하면서 찾는 방식입니다.

1. 배열을 오름차순으로 정렬

2. 중간값(low + high)인 Mid를 정합니다.

3. 자신이 찾길 원하는 원소(target)와 mid를 비교합니다.

4. target보다 mid가 더 큰 경우 mid를 기준으로 더 큰 원소들은 볼 필요가 없기 때문에 low= Mid + 1

   target보다 mid가 더 작을 경우 mid를 기준으로 더 작은 원소들은 볼 필요가 없기 때문에 high= Mid - 1

5. low가 high보다 커질 경우 반복문을 멈춥니다.

 

<이진검색을 통해 원하는 원소를 탐색하는 자바 코드>

public class Main {
    public static int binarySearch(int[] arr, int target){
      int low = 0, high = arr.length-1;
      int index = 0;

      while(high >= low){
        int mid = (low+high) / 2;
        if(target == arr[mid]){
          index = mid + 1;
          break;
        } else if(target < arr[mid]){
          high = mid-1;
        } else{
          low = mid+1;
        }
      }

      return index;
    }

    public static void main(String[] args){
      int[] arr = {2, 9, 13, 53, 90, 98};
      int target = 90;
      System.out.println(binarySearch(arr, target));
    }
  }

▷ 이진검색의 특징

• 장점

    1. 처음부터 끝까지 탐색하는 순차 탐색에 비해 굉장히 효율적입니다.

 

• 단점

    1. 데이터가 미리 정렬된 리스트라는 조건이 요구됩니다.

▷ 이진검색의 시간복잡도

데이터의 개수가 n개라고 했을 때

• 최선의 경우 : O(n)
• 최악의 경우(자료가 역순인 경우) : O(logN)

    연산 횟수

    처음 입력된 갯수를 N이라 했을 때

    첫번 째 수행 : N의 반을 버려 N = N * ½이 됩니다.

    두번 째 수행 : 그 중 다시 반을 버리므로 N * ½ * ½

    ...

    K번 째 수행 : N * (½)의 K승

    마지막 수행이 끝나고 난 뒤 1(N이 1이 되므로) = N * (½)의 K승입니다.

    양변에 2 K승을 곱하면 2 K승 = N 이므로 시행 횟수인 K는 Log2N이 되며

    따라서 시간 복잡도는 O(logN)이 됩니다.

▷ 참고

• https://jorgechavez.dev/2020/08/22/everything-you-need-to-know-about-binary-search-algorithm/