[코딩테스트]이진탐색

책 '이것이 취업을 위한 코딩 테스트다'를

기반으로 공부하였습니다.

https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

1. 이진탐색 : 얻고자하는 데이터를 탐색하는데, 해당 배열이 정렬되있다고 가정했을 때, 사용할 수 있는 탐색알고리즘입니다. 탐색할 배열의 양을 반씩 줄여나가서 하나씩 탐색하는 순차탐색보다 시간복잡도가 낮습니다.

 

1-1) 재귀함수를 통한 이진탐색 구현

public static int binary_search1(int[] arr,int start, int end, int target) {
		if(start>end) {
			return -1;
		}
		int mid = (start+end)/2;
		if(arr[mid]==target) {
			return mid;
		}
		else if(arr[mid]>target) {
			return binary_search1(arr,start,mid-1,target);
		}
		else {
			return binary_search1(arr,mid+1,end,target);
		}
	}

 

1-2) 반복문을 통한 이진탐색 구현

public static int binary_search2(int[] arr,int start, int end, int target) {
		while(start<=end) {
			int mid = (start+end)/2;
			if(arr[mid] == target) {
				return mid;
			}
			else if(arr[mid]> target) {
				end = mid-1;
			}
			else {
				start = mid+1;
			}
		}
		
		return -1;
	}