본문 바로가기
스터디/알고리즘

[알고리즘] 이분탐색/이진탐색 Binary Search

by naahy 2024. 8. 13.

이분 탐색

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘

찾고자 하는 값과 중간값을 반복적으로 비교해 탐색 범위를 절반씩 좁혀가며 데이터를 탐색함

변수 3개(high, low, mid) 사용

 

  1. 처음 리스트의 중간값을 임의의 값으로 선택 mid = (low + high) / 2
  2. 그 값과 찾고자 하는 값의 크고 작음을 비교
    1. 처음 선택한 중앙값이 만약 찾는 값보다 크면(mid > key) 그 값은 새로운 최댓값이 됨 (high = mid - 1)
    2. 작으면(mid < key) 그 값은 새로운 최솟값이 됨 (low = mid + 1)
    3. 같으면 (mid == key) 중간값 리턴 후 종료

찾고자 하는 값이 7일 경우

 

장점

검색이 반복될 때마다 탐색 범위가 반으로 줄어들어 목표값을 찾을 확률이 두 배가 되므로 속도가 빠름

시간 복잡도: O(log N)

비교 횟수 범위
0 n
1 n / 2
2 n / 2^2
... ...
k n / 2^k

n / 2^k = 1 이므로 k 값은 log2 n

 

단점

정렬된 리스트에만 사용 가능

 

의사코드

재귀호출

BinarySearch(A[0..N-1], value, low, high) {
  if (high < low)
    return -1 // not found
  mid = (low + high) / 2
  if (A[mid] > value)
    return BinarySearch(A, value, low, mid-1)
  else if (A[mid] < value)
    return BinarySearch(A, value, mid+1, high)
  else
    return mid // found
}

 

반복

binarySearch(A[0..N-1], value) {//k
  low = 0
  high = N - 1
  while (low <= high) {
      mid = (low + high) / 2
      if (A[mid] > value)
          high = mid - 1
      else if (A[mid] < value)
          low = mid + 1
      else
          return mid // found k
  }
  return -1 // not found k
}

 

반복 구조를 사용하는 것이 재귀 호출을 사용하는 것보다 더 효율적임

 

자바

public int binarySearch(int[] arr, int target) {
    int start = 0;
    int end = arr.length - 1;
    int mid = 0;

    while (start <= end) {
        mid = (start + end) / 2;
        if (target == arr[mid]) {
            return mid;
        }else if (arr[mid] < target) {
            start = mid + 1;
        }else if (target < arr[mid]) {
            end = mid - 1;
        }
    }
    throw new NoSuchElementException("can't find target.");
}

 

 

출처

 

저작자표시

'스터디 > 알고리즘' 카테고리의 다른 글

[알고리즘] 누적합 알고리즘 (Prefix sum algorithm)  (0) 2024.11.05

관련글

댓글

티스토리툴바