이진탐색(Binary Search) 알고리즘

이진 탐색 알고리즘

---

• 이진 탐색 알고리즘이란?
  데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.
  정렬된 배열의 중간에 임의의 값을 찾고자하는 값과 비교하여, 1) 만약 중간의 값이 더 작다면 중간의 값을 제외한 배열의 우측 데이터들을 대상으로 탐색을 진행하고 2) 만약 중간의 값이 더 크다면 중간의 값을 제외한 배열의 좌측 데이터들을 대상으로 탐색을 진행하고 3) 만약 중간의 값과 찾고자 하는 값이 동일하다면 알고리즘을 중단한다.

이진 탐색 알고리즘의 시간 복잡도

---

이진 탐색 알고리즘은 중간 값과 찾고자하는 값의 비교가 이루어질때마다 탐색 범위가 1/2로 줄어든다.
정렬된 데이터의 크기를 n으로, 비교 횟수를 k라고 정의하자.

n * (2/1)^k = 1
n = 2^k
k = log n

즉, n크기의 데이터에 대한 이진탐색 알고리즘의 시간복잡도는 다음과 같다.
T(n) = θ(log n)

이진 탐색 알고리즘의 장점과 단점

---

• 이진 탐색 알고리즘의 장점
  - 선형 탐색과 비교하여 탐색 시간이 빠르다. (선형 탐색의 경우 시간 복잡도는 T(n) = θ(n)이다. )
• 이진 탐색 알고리즘의 단점
  - 정렬된 리스트에서만 사용될 수 있다.
  

이진 탐색 알고리즘의 구현

---

• 핵심 코드

 int binary_search(int* data_arr, int target) {
      int left = 0, right = SIZE - 1;
      
      while (left <= right) {
          int mid = (left + right) / 2;
          if (data_arr[mid] == target) return mid;
          else if (data_arr[mid] > target) right = mid - 1;
          else left = mid + 1;
      }
      
      return -1;
  }

• 전체 코드
  - ssuda0/Algorithm/SearchAlgorithm/binarysearch.cpp

이진 탐색 문제

---

문제 번호	정답률	출처	난이도(5)	전체 코드	문제 풀이
1920 : 수 찾기	28.032%		1	1920.cpp	X
2110 : 공유기	48.796%		2	2110.cpp	O
2805 : 나무 자르기	25.503%	COCI	1	2805.cpp	X
2512 : 예산	31.284%	Olympiad	2	2512.cpp	X
2343 : 기타 레슨	28.797%		2	2343.cpp	X
3691 : 컴퓨터 조립	47.945%	ICPC