📌 이진 탐색(Binary Search) 란?
이진탐색(Binary Search)은 정렬된 배열이나 리스트에서 특정 값을 찾기 위한 효율적인 알고리즘이다.
배열의 중간 요소를 선택해 일치하면 검색 종료.
중간 요소가 찾는 값보다 크면 왼쪽 부분, 작으면 오른쪽 부분 배열에서 계속 검색.
이렇듯 계속해서 배열의 부분배열을 반복적으로 나누며 검색한다.
- 계속해서 배열을 반으로 나누며 검색을 한다.
- 정렬이 되어 있어야만 사용 가능하다.
- Up/Down 게임과 원리가 같다.
- 시간 복잡도는 O(log n)이다.
구현 코드
static int BinarySearch(int[] arr, int target)
{
int left = 0; // 왼쪽 시작
int right = arr.Length - 1; // 오른쪽 시작
while (left <= right) // 왼쪽이 오른쪽보다 커질 때 까지 반복
{
int mid = left + (right - left) / 2; // 왼쪽, 오른쪽 중간값
if (target == arr[mid]) // 찾는 값이면 index mid return
return mid;
if(arr[mid] < target) // 찾는 값보다 작으면(왼쪽이면) left를 mid + 1
left = mid + 1;
else // 찾는 값보다 크면(오른쪽이면) right를 mid - 1
right = mid - 1;
}
return -1;
}
target == 18
mid = 0 + (9 - 0) / 2 = 4
if(arr[mid] < target) left = mid + 1 = 5
mid = 5 + (9 - 5) / 2 = 7
if(arr[mid] < target) left = mid + 1 = 8
mid = 8 + (9 - 8) / 2 = 8
arr[mid] == target
return 8
공부하다 보니 알아낸 디테일 중 하나는
왜 mid를 (left + right) / 2를 하지 않고
left + (right - left) / 2를 했는가 인데
그 이유는 위 방식으로 하면 int의 최댓값을 넘어가버려서 원하는 값을 찾지 못하는 경우가 생기기 때문에
right - left로 int 최댓값을 넘어가는 것을 방지하기 때문이다.
