[알고리즘] 탐색 Search (Java, Python)

🕵️ 탐색

순차 탐색 Sequential Search

: 앞에서부터 차례대로 탐색 (= Single Search)

→ 시간복잡도 O(n)

• Java

public int SequentialSearch(int[] arr, int target) {
  for(int i = 0; i < arr.length; i++) {
  	if(arr[i] == target) {
      return i;
    }
  }
  return -1;
}

• Python

def sequential_search(num_list, target):
  for i in range(len(num_list)):
    if num_list[i] == target:
      return i
  return None

 

 

이진 탐색 Binary Search

: 오름차순으로 정렬된 자료에 대해 탐색의 범위를 절반씩 좁혀가며 탐색

→ 시간복잡도 O(lg n)

반복문을 활용한 구현

• Java

public int BinarySearch(int[] arr, int target) {
	// arr 내 탐색범위 설정
	int start = 0;
    int end = arr.length - 1;
    
    // start와 end가 역전되기 전까지 이진 탐색
  	while(start <= end) {
    	int mid = (end - start) / 2;
        
    	if(arr[mid] == target) {		// 탐색 완료
        	return mid;
        } else if(arr[mid] > target) {	// 왼쪽 탐색
        	end = mid - 1;
        } else {						// 오른쪽 탐색
        	start = mid + 1;
        }
  	}
    // 탐색범위에 target 없음
    return -1;
}

• Python

def binary_search(num_list, target):
	start, end = 0, len(num_list) - 1
    
    while start <= end:
    	mid = (end - start) // 2
        
        if num_list[mid] == target:
        	return mid
        elif arr[mid] > target:
        	end = mid - 1
        else:
        	start = mid + 1
            
    return None
  
  

재귀함수를 활용한 구현

• Java

public int class BSearchRecur(int[] arr, int target, int start, int end) {
	// base case
    if(start > end) {
    	return -1;
    }
    
    // recursive case
    int mid = (end - start) / 2;
    if(arr[mid] == target) {
    	return mid;
    } else if(arr[mid] > target) {
    	BSearchRecur(arr, target, start, mid - 1);
    } else {
    	BSearchRecur(arr, target, mid + 1, end);
    }

• Python

def b_search_recur(num_list, target, start, end):
	# base case
    if start > end:
    	return None
        
    # recursive case
    mid = (end - start) // 2
    if num_list[mid] == target:
    	return mid
  	elif num_list[mid] > target:
    	b_search_recur(num_list, target, start, mid - 1)
    else:
    	b_search_recur(num_list, target, mid + 1, end)