[알고리즘] 이진 검색 (Binary Search) - JAVA / 자바

이진 검색(Binary Search, 이분 검색, 보간 검색(Interpolation Search))

 - 자료의 가운데 있는 항목을 키 값과 비교하여 다음 검색 위치를 결정하여 검색을 계속하는 방법

    ㄴ 찾는 키 값 > 원소의 키 값 : 오른쪽 부분에 대해 검색 실행

    ㄴ 찾는 키 값 = 원소의 키 값 : 검색 성공

    ㄴ 찾는 키 값 < 원소의 키 값 : 왼쪽 부분에 대해 검색 실행

 - 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가며 더 빠르게 검색

 - 정복 기법을 이용한 검색 방법 : 검색 범위를 반으로 분할하는 작업과 검색 작업 반복 수행

 - 정렬되어 있는 자료에 한해서 검색 가능

 

Ex) 리스트 = {1, 3, 10, 23, 29, 33, 45, 50}

1

3

10

23

29

33

45

50

1. 29 검색 = 4 (검색 성공)

① 29 > 23	1	3	10	23	29	33	45	50
오른쪽 검색				기준값	◀ 검색 범위 ▶
② 29 < 33	1	3	10	23	29	33	45	50
왼쪽 검색					◀ 검색 범위 ▶	기준값
③ 29 = 29	1	3	10	23	29	33	45	50
검색 성공					기준값

ANS = 4 (검색 성공)

 

2. 11 검색 = 검색 실패

① 11 < 23	1	3	10	23	29	33	45	50
왼쪽 검색	◀ 검색 범위 ▶			기준값
② 11 > 3	1	3	10	23	29	33	45	50
오른쪽 검색		기준값	◀ 검색 범위 ▶
③ 11 ≠ 10	1	3	10	23	29	33	45	50
검색 실패			기준값

ANS = 검색 실패

 

 알고리즘 

binarySearch(list[], low, high, key)
    middle ← (low + high) / 2;
    if (key = list[middle]) then return i;
    else if (key < list[middle]) then binarySearch(list[], low, middle-1, key);
    else if (key > list[middle]) then binarySearch(list[], middle+1, high, key);
    else return -1;
end binarySearch()

★삽입이나 삭제가 발생할 경우 항상 배열이 정렬 상태로 유지되도록 하는 추가 작업 필요★

시간 복잡도 : O(log2 n)

---

이진트리 검색(Binary Tree Search)

 - [자료구조] 이진 탐색 트리 Binary Search Tree를 사용한 검색 방법

[자료구조] 이진 탐색 트리 Binary Search Tree

 - 원소의 삽입이나 삭제 연산에 대해 항상 이진 탐색 트리를 재구성하는 작업 필요

 

---

< 분류 >

검색 방식 - 비교 검색(Comparison Search)

[자료구조] 검색 (Search)