Binary Search

 

❒ Description

---

이분 탐색의 동작과정을 정리하자.

 

 

 

 

 

❒ Binary Search

---

 

이진 검색이란 정렬된 배열에서  타깃을 찾는 검색 알고리즘이다. 어떠한 경우에는 O(logN)의 시간복잡도를 갖는다.

 

동작 방식은 아래와 같다.

 

 

 

 

 

 

❒ 효율적인 중앙 찾기

---

만약 아래와 같이 중앙 위치를 찾는면 중앙 값은 0이 나오게 된다.

int start = Integer.MAX_VALUE;
int end = Integer.MAX_VALUE;
int mid = (start + end) / 2;

그 이유는 start와 end의 합이 자료형의 최댓 값을 넘어가기 때문이다. 

 

이런 경우를 방지하기 위해서 다음과 같이 중앙 값을 찾아야 한다.

int start = Integer.MAX_VALUE;
int end = Integer.MAX_VALUE;
int mid = start + (start - end) / 2;

 

 

 

 

 

 

---