[Java알고리즘] Ch 3-2. 검색 _ 이진 검색

1. 이진 검색

'이진 검색'을 적용하기 위해서는 데이터가 키 값으로 이미 정렬(sort)되어 있어야한다.
'이진 검색'은 '선형 검색'보다 빠르다.
❗️정렬 (sort) : 오름차순, 내림차순 등

• 검색을 한단계 진행할 때 마다, 검색 범위가 거의 반으로 좁혀진다.

  1. 맨 앞 인덱스를 p1 ,맨 끝 인덱스를 pr, 중앙 인덱스를 pc라고 예를들면
  2. 검색을 시작할 때, p1은 0, pr은 n-1, pc는 (n-1)/2 로 초기화 한다.
  3. 검색범위를 좁힌다.
     3-1. a[pc] < key 일 경우, 검색범위를 뒤쪽으로 좁힌다.
     3-2. a[pc] > key 일 경우, 검색범위를 앞쪽으로 좁힌다.
     3-3. a[pc] == key 일 경우, 검색 성공!!
  4. 위의 과정을 p1이 pr보다 작거나 같은 경우에 계속 반복한다.
  5. p1이 pr보다 커졌음에도 (배열의 끝까지 모두 탐색) 검색을 성공하지 못했다면, 검색 실패를 return 한다.

2. 이진 검색으로 키 값 idx 찾기

3. 복잡도 (complexity)

프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라진다.
알고리즘의 성능을 객관적으로 평가하는 기준을 '복잡도(complexity)'라고 한다.

복잡도 요소
1. 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것
2. 공간 복잡도(space complexity): 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

4. Arrays.binarySearch에 의한 이진 검색

Java는 배열에서 이진검색을 하는 메소드를 표준 라이브러리로 제공한다.
java.util.Arrays 클래스의 binarySearch 메소드가 있다.

1. 이진 검색 메소드를 직접 코딩할 필요가 없다.
2. 모든 자료형 배열에서 검색할 수 있다.

❗️ API 문서 보기
https://docs.oracle.com/javase/8/docs/api/