[Java/Algorithm]이진검색 Binary search

 

이진 검색
Binary search

※이진 검색은 정렬sort되어 있는 값을 대상으로 검색합니다.
선형 검색보다 효율이 좋습니다(빠릅니다.).

• 배열에서 인덱스의 처음, 중앙, 끝에 이름을 붙인다면
  → pl, pc, pr 이라 지정합니다.

	pl				pc				pr
인덱스	0	1	2	3	4	5	6	7	8
값	5	15	28	31	39	58	68	70	95

• 검색을 시작하기 전 이 셋을 아래와 같이 초기화합니다.
  • pl : 0
  • pc : (n - 1) / 2
  • pr : n-1
• 검색할 값이 중앙값pc보다 큰/작은 지 에 따랑 검색 범위가 반으로 좁혀집니다.
  → ex) 찾는 값이 15일 경우, pc보다 작으므로 범위가 pl ~ pc로 좁혀집니다.
• 범위를 반으로 줄이는 이 과정을 찾는 값이 나올 때까지 계속해서 반복합니다.

예시는 아래..

---

종료조건

1. pc와 찾는 값 key가 일치하는 경우 (검색 성공)
2. 검색 범위가 없는 경우 (검색 실패)

---

code

책 본문에 나온 내용에서 입력값을 Random으로, array를 list로 바꿔서 정렬후 사용하였습니다.

• 반복문 안에서 중앙값pc가 찾는값key와 일치하도록 좁혀가는 방법입니다.

  

• 중앙값pc가 key보다 작으면
  → 검색범위에서 요소의 시작을 중앙 뒤 인덱스로 바꾼다.
  

  

• 반대로 중앙값pc가 key보다 크면
  → 검색범위에서 요소의 끝은 중앙 앞 인덱스로 바꾼다.