이분 탐색이란 ?

• 오름차순 또는 내림차순으로 정렬된 배열에서 특정 값을 찾는 알고리즘
• 이분 탐색은 탐색 범위를 절반씩 줄여 나가기 때문에 빠른 속도를 보장한다.
  • 단, 배열이 정렬되어 있어야 한다.

이분 탐색 과정

• 낮은 인덱스의 변수명 : low
  • 초기 값 : 0
• 높은 인덱스의 변수명 : high
  • 초기 값 : 배열의 길이 - 1
• 중간 인덱스의 변수명 : mid
  • 값 설정 식 : (low + high) / 2

1. 배열의 중간 값을 선택하여 찾고자 하는 값과 비교한다.

2. 만약, 중간 값이 찾고자 하는 값보다 크면 중간 값 왼쪽 부분에서 탐색을 진행하고

    값보다 작으면 중간 값 오른쪽 부분에서 탐색을 진행한다. 
   

• 중간 값이 찾고자 하는 값보다 클 경우 : 중간 값에 1을 빼서 왼쪽 절반을 탐색한다.

if (arr[mid] > key) {
	high = mid - 1;
}

• 중간 값이 찾고자 하는 값보다 작을 경우: 중간 값에 1을 더해서 오른쪽 절반을 탐색한다.

if (arr[mid] < key) {
	low = mid + 1;
}

3. 이 과정에서 찾고자 하는 값이 나올 때까지 반복한다.

이분 탐색의 성능

• 이분 탐색의 시간 복잡도는 O(logn)으로 다른 정렬에 비해 상대적으로 매우 빠르다.

이분 탐색의 문자열 탐색

• 문자열 배열의 경우 이분 탐색을 사용하는 경우 Arrays.binarySearch() 함수를 이용할 수 있다.

• public static int binarySearch(Object[] a, Object key)

  • 매개변수로 주어진 배열에서 원하는 값을 이분 탐색하여 인덱스를 반환한다.
  • 만약, 해당 원소가 배열에 없다면 음수를 반환한다.
  • 무조건 위 함수를 호출하기 전에 배열을 정렬해야 한다 !!
  • Object[] a : 탐색하고자 하는 배열
  • Object key : 배열에서 찾으려는 값