목록Algorithm (1)
선진이네
[Algorithm] 이분 탐색
이분 탐색 순차적으로 탐색하는 것보다 시간 복잡도가 낮은 알고리즘으로 중간 값을 찾아나가는 과정이다. 알고리즘을 풀고 있는 인원들이라면 반복문을 이용한 순차적 탐색이 익숙할 것이다. 이분 탐색은 두 개의 깃발을 꽂고 중간 값을 통해 원하는 값을 찾아나가는 과정이다. 예를 들어, 1~10 정수 중 7이라는 정수를 찾아야하는 문제가 존재한다면 순차적 탐색은, 반복문을 통해 7번째에 원하는 값을 찾을 수 있다. 하지만 이분 탐색은 1~10의 중간값인 5를 찾고 6~10의 중간값인 8을 찾고, 6과 8의 중간 값인 7을 찾게 되어 3번째에 원하는 값을 찾게 된다. 이렇게 적은 인덱스에서 해를 구한다면 큰 차이를 느끼지 못할 수 있겠지만 무한히 커지는 인덱스라면 그 차이는 점점 커질 수 밖에 없을 것이다. 실제로..
Algorithm
2023. 9. 6. 23:05