개발을 시작하시는 여러분, 정보가 너무 많고 배워야 할 것도 산더미라 어디서부터 시작해야 할지 막막하신가요? 내일배움캠프 수료생들이 4개월 동안 배운 엄선된 핵심 개념을 직접 정리해서 알려 드립니다. 공부하다 막히거나 헷갈리는 개념이 있다면 개념 콕으로 정리해보세요.
이분 탐색 (Binary Search)
이분 탐색이란?
이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘입니다. 탐색 범위를 반복적으로 절반씩 줄여가면서 찾고자 하는 값을 찾는 방법입니다.
이분 탐색의 시간 복잡도는 O(logN) 입니다.
이분 탐색 원리
이분 탐색은 오름차순으로 정렬된 데이터 상태에서 4가지 과정을 반복합니다.
- 현재 데이터에서 중앙값을 선택합니다.
- 중앙값 > 타겟 일 때 중앙값 기준 왼쪽의 데이터를 선택합니다.
- 중앙값 < 타겟 일 때 중앙값 기준 오른쪽의 데이터를 선택합니다.
- 위 과정을 반복하다 중앙값 == 타겟 데이터일 때 탐색을 종료합니다.
예를 들어, 정렬된 배열 [1, 15, 32, 45, 67, 88, 97, 120, 150]에서 97을 찾는 과정을 단계별로 살펴보겠습니다.
초기 상태
- 배열: [1, 15, 32, 45, 67, 88, 97, 120, 150]
- 찾고자 하는 값: 97
- 시작 인덱스(low): 0
- 끝 인덱스(high): 8
1단계
- 중간 인덱스(mid) 계산: (0 + 8) / 2 = 4
- 중간 인덱스의 값(arr[mid]): 67
- 67 < 97이므로, 탐색 범위를 오른쪽 절반으로 좁힙니다.
- low = mid + 1 = 5
- high = 8
2단계
- 중간 인덱스(mid) 계산: (5 + 8) / 2 = 6
- 중간 인덱스의 값(arr[mid]): 97
- 97 == 97이므로, 탐색을 종료하고 인덱스 6을 반환합니다.
만약 찾고자 하는 값이 배열에 없다면, low가 high보다 커지는 시점에 탐색이 종료되고 해당 값이 없다는 것을 알 수 있습니다.
이분 탐색 과정을 통해 3번의 비교만으로 97의 위치를 찾을 수 있었습니다. 만약 순차 탐색을 사용했다면 최대 7번의 비교가 필요했을 것입니다. 이분 탐색은 정렬된 배열에서 빠르게 값을 찾을 수 있는 효율적인 알고리즘입니다. 배열의 크기가 클수록 이분 탐색의 성능 이점이 더욱 두드러집니다.
내일배움캠프는 개발에 필요한 핵심만 배웁니다
지금까지 꼭 필요한 개발 지식에 대해 알아보았습니다. 내일배움캠프에서는 전문가들이 선별한 핵심 개발 지식으로 개발 공부도, 취업도 보다 효율적으로 할 수 있는데요. 국내 유수의 IT기업 출신 튜터님들과 실습 위주의 독보적인 커리큘럼으로 개발자 취업을 체계적으로 준비해보세요. 내일배움캠프 4개월, 여러분 인생의 가장 큰 터닝 포인트입니다.
CREDIT
글 | 조원호 내일배움캠프 수료생
편집 | 정효재 팀스파르타 에디터
취업 준비, 어디서부터 시작해야 할지 모르겠다면?
🧐비전공자인데 IT 업계 취업할 수 있을까?
😟프로젝트 경험이 부족한데, 어떻게 준비해야 할까?
🥺IT 기업으로 이직하고 싶은데 뭐부터 시작해야 할까?
이런 고민을 하고 있다면, 내일배움캠프의 IT 취업 컨설팅을 받아보세요.
취업 코칭 전문가들이 여러분의 고민을 해결해 드립니다.
다음 링크에 이메일을 입력하시면 메일로 1:1 커리어 상담권과 취준 자료집을 보내드릴게요.
Share article
Subscribe to our newsletter