[이코테 - 7] 이진 탐색

 

이진탐색

이진탐색이란, 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 시작점, 끝점, 중간점을 배열의 인덱스로 정의하고, 찾고자하는 값과 중간점을 비교하여 탐색 범위를 반씩 줄인다. 이와 반대되는 개념으로 순차탐색이 있는데, 순차탐색은 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이다.

 이진탐색은 데이터가 정렬되어있어야 하고, 시간 복잡도는 O(log N)이다. 순차탐색의 시간복잡도는 O(N)이다.

이진탐색에서의 시작점, 중간점, 끝점

 

 

이진탐색 코드 <Python>

def binary_search(array, target, start, end):
	while start <= end:
    	mid = (start +end) // 2
        if array[mid] == target:
        	return mid
        elif array[mid] > target:
        	end = mid - 1
        else:
        	start = mid + 1
    	return None
    
n,target = list(map(int,input().split()))
array = list(map(int,input().split())))

result = binary_search(array, target, 0, n-1)

 

이진탐색 코드 <JavaScript>

function binarySearch(arr, target) {
	let left = 0;
        let right = arr.length - 1;

        while (left <= right){
            let mid = Math.floor((left+right) / 2); //소수점 버리고 가장 가까운 작은 정수로
            if (arr[mid] === target) return mid;
            else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
                }
            }
            return -1;
    }