6. 이진 탐색 알고리즘

6. 이진 탐색 알고리즘

순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인 하는 방법

하는 방법 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

하는 방법

주의할 점은 해당 알고리즘은 정렬되어있는 경우에 사용할 수 있다는 것이다.

만약 정렬이 되어있지 않은 경우에는 시간 복잡도가 '정렬 시간 복잡도' * '이분 탐색 시간 복잡도'라고 생각해야 한다.

이진 탐색의 시간 복잡도

단계마다 탐색 범위를 2로 나누는 것과 동일하다. (연산 횟수는 log(2)N에 비례한다. '()'는 밑을 의미)

다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장한다.

public class BinarySearch { private static int search(int[] arr, int target) { int start = 0; int end = arr.length - 1; while (start <= end) { // while문 대신 재귀적으로 동작시킬 수도 있지만 while 방식이 좋다. int mid = (start + end) / 2; if (arr[mid] == target) { return mid; } if (arr[mid] > target) { end = mid - 1; continue; } start = mid + 1; } return -1; } public static void main(String[] args) { int[] arr = {1, 4, 7, 10, 15, 19, 21, 23}; int target = 21; int resultPosition = BinarySearch.search(arr, target); System.out.println("결과 index: " + resultPosition); } }

이미 Java 라이브러리에는 binarySearch 함수가 존재한다! 이를 활용해도 좋다!

추가적으로 만약 라이브러리로 없는 target으로 함수를 실행시키면, target으로 지정한 값보다 바로 다음으로 큰 값의 index를 음의 값으로 가진채로 리턴한다.

Java 라이브러리가 제공하는 binarySearch의 알고리즘을 까보면 아래와 같다.

더보기 >>> 가 뭐였지하고 가물가물했는데... 비트 연산자 였다. 참고자료

파라메트릭 서치(Parametric Search)

파라메트릭 서치 란 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법이다. 예시: 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

란 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법이다. 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.

주어진 문제가 큰 탐색 범위를 가진다면... 가장 먼저 이진 탐색을 떠올려야 한다.

from http://rok93.tistory.com/184 by ccl(A) rewrite - 2021-09-30 06:02:12