목록이분탐색이란 (1)

KKanging

[알고리즘] 이분 탐색이란(Binary Search)

이분 탐색이란 이분 탐색의 특징 일반적으로 크기가 N인 배열이 순서대로 정렬되어 있을 때 사용할 수 있다. 수행시간이 O(logn)으로 완전 탐색 알고리즘 보다 훨씬 단축된다. 이분탐색은 왜 필요로 할까 위와 같은 N=5 배열이 있고 우리는 배열의 원소를 찾는 과정을 수행한다고 가정해보자 만약 브루트 포스 알고리즘 ( 완전 탐색 알고리즘)을 사용한다면? 1을 찾는다면 한번에 찾을 수 있다. 하지만 20을 찾는다면 20을 찾을 때까지 5번의 수행을 해야한다. 위 예시는 배열의 크기가 작지만 1024개의 크기라고 가정하면 1024번을 수행한다. 이분탐색의 원리 찾는 대상 20 mid 인덱스 값을 구한다 이때 mid 인덱스는 탐색하는 배열의 첫 원소와 마지막 원소의 인덱스의 중간값이다. mid = (start..
cs/알고리즘 2023. 8. 13. 17:47
이전 Prev 1 Next 다음