이분 탐색/이진 탐색(Binary Search)

이진 탐색 알고리즘은 정렬된 원소 리스트를 받아 리스트에 원하는 원소가 있을경우 그 원소의 위치를 반환, 없을경우 null을 반환함.

시간복잡도는 O(log n)으로 매우 빠른편.

 

 

https://brilliant.org/wiki/binary-search/

 

Java 구현 코드

static int binarySearch(int[] arr, int num) {
  Arrays.sort(arr);

  int l = 0, r = arr.length-1;

  while(l <= r) {
    // 중간 위치 구함
    int mid = (l + r)/2;

    // 위치를 찾았을 경우
    if(arr[mid] == num) return mid;

    // 중간 값이 찾고자하는 값보다 작을 경우 == 중간 값 보다 오른쪽에 위치해있다
    if(arr[mid] < num) {
    	l = mid + 1;
    }else {	// 중간 값이 찾고자하는 값보다 큰 경우 == 중간 값 보다 왼쪽에 위치해있다
    	r = mid - 1;
    }
  }

  // 찾는 값이 없을 경우 -1을 반환(-1이라는 index는 없기 때문)
  return -1;
}