[알고리즘] 이분탐색

이분탐색이란?

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

반드시 정렬된 리스트에서 사용해야함! 자료가 무작위로 있다면 어느 특정 방향(앞 또는 뒤)으로 간다고 해서 해당 자료가 중간 부분보다 작거나 크다는 보장이 없음.

 

구현 과정

• 리스트 오름차순으로 정렬

• 찾고자 하는 범위의 최솟값(left) / 최댓값(right) / 리스트의 중간 값(mid) 선택, 찾고자 하는 값 X와 비교
  • X가 mid보다 작으면 mid보다 작은 값들을 대상으로 다시 탐색 (mid = X - 1)
  • X가 mid보다 크면 mid보다 큰 값들을 대상으로 다시 탐색 (mid = X + 1)
• 해당 X값을 찾을 때까지 반복
  • 단, left가 right보다 커지면 반복 중단

 

 

구현 코드

int[] array = {10, 23, 34, 45, 66, 88};
int X = 23; // 찾고자 하는 값

int left = array[0];
int right = array[array.length - 1];

while (left <= right) {
  int mid = (left + right) / 2;

  if (mid < X) { 
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}

 

 

복잡도

 

 

 

---

참고링크

위키백과

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제

이진 탐색과 시간 복잡도 분석 (Binary Search and its Time Complexity Analysis)