순차적 탐색

• 정렬되지 않은 배열 안에서 특정 원소를 찾기 위해 인덱스 0부터 마지막까지 하나씩 차례대로 탐색
• 시간 복잡도: O(n)
  

이진 탐색

• 정렬된 배열 안에서 특정 원소를 찾기 위해 중앙에 있는 값을 조사하여 찾고자 하는 원소가 왼쪽 혹은 오른쪽 배열에 있는지를 알아내 탐색의 범위를 반으로 줄여가며 탐색
• 시간복잡도: O(logn)
• 자료들이 배열에 저장되어 있어 삽입/삭제가 매우 비효율
  

구현 코드

반복문 구현

static boolean BSearch(int[] arr, int n) {
	int left = 0;
    int right = arr.length - 1;
    int mid;
    
    while(left <= right) {
    	mid = (left + right) / 2;
        if (arr[mid] < n) 
        	left = mid + 1;
        else if (arr[mid] > n) 
        	right = mid - 1;
        else
        	return true;
    }
    return false;
}

재귀 구현

static boolean BSearch(int[] arr, int n, int left, int right) {
	 if (left > right) 
     	return false;
    int mid = (left + right) / 2;
    if (arr[mid] < n)
    	return BSearch(arr, n, mid +1, right);
    else if (arr[mid] > n)
    	return BSearch(arr, n, left, mid - 1);
    else
    	return true;
}

이진 탐색 트리

• 이진 탐색과 근본적으로 같은 원리에 의한 탐색 구조
• 시간복잡도
  • 균형트리: O(logn)
  • 불균형트리: O(N) ➡️ 순차적 탐색과 동일
    
• 삽입/삭제 매우 빠름