Algorithm | Binary Search

Binary Search

 이진 탐색(Binary Search)은 오름차순으로 정렬된 배열에서 특정한 값의 위치를 찾는 알고리즘이다. 이진 탐색의 과정은 다음과 같다.

 

1. 배열의 중간에 위치한 임의의 값을 선택한다. 

2. 선택된 값과 찾고자 하는 값 X와 비교한다.

3-1. X가 더 작으면 중간값을 기준으로 왼쪽에 있는 데이터들을 대상으로 1 - 3번을 반복한다.

3-2. X가 더 크면 중간값을 기준으로 오른족에 있는 데이터들을 대상으로 1 - 3번을 반복한다.

 

 예시를 통해 이진 탐색을 이해해보자. {1, 5, 6, 8, 11, 15, 30, 33, 35, 48}의 배열에서 5를 찾아보자.

 

<1차 시도>

{1, 5, 6, 8, 11, 15, 30, 33, 35, 48}에서 11을 중간값으로 선택하고 5와 비교한다. 5 < 11 이므로 왼쪽의 데이터들을 이용하자.

 

<2차 시도>

{1, 5, 6, 8}에서 5를 중간값으로 선택하고 5와 비교한다. 찾으려는 데이터와 일치하므로 알고리즘을 종료한다.

Binary Search 구현(in JAVA)

public int search(int[] arr, int start, int end, int x) {
  if(start > end) {	// 시작 인덱스가 마지막 인덱스보다 커지면 x가 배열 내에 없는 것
    return -1;	// -1 return
  }

  int mid = (start + end) / 2;	// 중간값의 인덱스
  
  if(arr[mid] == x) {	// 중간값이 x라면
    return mid;	// 중간값의 인덱스 return
  }else if(arr[mid] > x) {	// 중간값이 더 크다면
    return search(arr, start, mid-1, x);  // 중간값의 오른쪽에 위치한 데이터들을 대상으로 다시 search
  }else {	// 중간값이 더 작다면
    return search(arr, mid+1, end, x);  // 중간값의 왼쪽에 위치한 데이터들을 대상으로 다시 search
  }
}

 재귀 호출을 이용하여 이진 탐색을 구현해보았다. 반복문을 사용해서 구현하는 방법도 있다.

---

Reference

 

· https://cjh5414.github.io/binary-search/

· https://ledgku.tistory.com/35