자료구조_이진탐색 O(logN)

오름차순으로 정렬된 배열에 사용한다 

 

이진탐색 개념 이해

---

1,2,3....8,9,10 숫자 중에 7을 선택하였을때 그 숫자가 어디에 있는지 검색한다

 

(1) 배열의 길이를 2로 나누어 나온 인덱스 4의 값을 먼저 찾는다 

인덱스0	인덱스1	인덱스2	인덱스3	인덱스4	인덱스5	인덱스6	인덱스7	인덱스8	인덱스9
1	2	3	4	5	6	7	8	9	10
				(1)

(2) 찾으려는 7은 인덱스 4의 값인 5보다 크기 때문에 그 앞에 숫자는 제외한다

인덱스 5부터 인덱스 9 까지 범위 중 가운데 값을 찾아본다 

 

인덱스0	인덱스1	인덱스2	인덱스3	인덱스4	인덱스5	인덱스6	인덱스7	인덱스8	인덱스9
1	2	3	4	5	6	7	8	9	10
x	x	x	x	x			(2)

(3) 찾으려는 7은 인덱스 7의 값인 8보다 작기 때문에 그 뒤에 숫자는 제외한다 

인덱스 5 ~6 까지 범위 중 하나를 임의로 선택하여 값을 찾아본다 

인덱스0	인덱스1	인덱스2	인덱스3	인덱스4	인덱스5	인덱스6	인덱스7	인덱스8	인덱스9
1	2	3	4	5	6	7	8	9	10
x	x	x	x	x	(3)		x	x	x

 

(4) 찾으려는 7은 인덱스 5의 값인 6보다 크기 때문에 인덱스 5는 제외한다

인덱스 6의 값이 7이 맞는지 확인한다 

 

이것이 이진탐색이다 

 

이진탐색 코드 구현 풀이

---

(1) 첫번째, 마지막 인덱스, 중간지점을 변수로 지정한다 

int first =0 

int final = arr.length -1 

int center = (first +final )/2

 

 

(2) while 반복문 으로 실행하고 검색하는 원소가 남아있을때까지 수행한다 

찾는값 = center와 같으면 반환한다

찾는값 > center 이면 first를 +1 

찾는값 < center 이면 final를 -1 

해서 계속 값을 찾는다 

 

 

원소가 100개인 정렬된 배열의 이진탐색은 몇단계가 걸리는가? 7단계 

1단계	2단계	3단계	4단계	5단계	6단계	7단계	8단계	9단계	10단계
50	25	12	6	4	2	1

원소가 200개인 정렬된 배열의 이진탐색은 몇단계가 걸리는가? 8단계 

1단계	2단계	3단계	4단계	5단계	6단계	7단계	8단계	9단계	10단계
100	50	25	12	6	4	2	1

반응형