[알고리즘] 이진탐색(이분탐색) - Binary Search

Binary Search

---

정렬된 데이터 집합을 이분화 하면서 탐색하는 방법

정렬되어 있어야 한다

 

출처 : 네이버 지식백과

 

보통 세 개의 변수를 지정해 두고 (ex : left, mid, right)

찾고자 하는 값, 즉 mid의 값이 찾아낸 값보다 크면 mid는 찾아낸 값보다 오른쪽에 위치하고 작다면 왼쪽에 위치한다

public static int binarySearch(int arr[], int x) {
	
		int mid;
		int left = 0;
		int right = arr.length - 1;
	
		// 배열을 다 돌때까지 반복
		while (left <= right) {
			mid = (right + left) / 2;
	
			// 원하는 값이라면 해당 위치 반환
			if (arr[mid] == x) {
				return mid;
			}
	
			if (x < arr[mid]) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		// 원하는 값을 찾지 못할경우를 지정
		return -1;
	}
}