[Algorithm] 이진탐색

이진탐색(binary search)란?

정렬되어 있는 자료들의 집합에서 특정한 자료를 찾으려고 할때 사용되고 매우 빠른 검색 알고리즘이다. 원소를 반으로 분할해서 찾는 방법이다. 시간복잡도는 O(logN) 으로 전체탐색 O(N) 보다 빠르다.

그림출처

---

그림출처

---

이진탐색의 조건

• 정렬이 되어있어야 한다.

---

이진탐색 동작방식

1. 배열의 중간 값을 가져와서 찾으려고 하는 값과 비교를한다.
2. 중간값과 같다면 내가 원하던 값 이니 종료하고 크면 중간값기준 오른쪽 원소들을 대상으로 탐색한다.
   작으면 왼쪽 대상들을 탐색한다.

---

구현

public class 이진탐색 {

 public static void main(String[] args) {
		// TODO Auto-generated method stub
 	int[] arr = { 1, 7, 16, 25, 30, 33, 41, 66, 78, 90 };

	int num = 78; // 우리가 찾고 싶은 숫자

	int lowIndex = 0;
	int highIndex = arr.length - 1;

	while (true) {
		int centerIndex = (lowIndex + highIndex) / 2;

		if (arr[centerIndex] == num) {
			System.out.println(num + "은 " + centerIndex + "번째 숫자입니다.");
			break;
			}

      
		else if(arr[centerIndex]<num) {
			lowIndex = centerIndex+1;
				
			}
		else { //arr[centerIndex]>num 
			highIndex = centerIndex-1;
				
			}

		}

	}

---

참고

opd's document - 이진탐색
TechInterview - 이분탐색