[알고리즘 with JS] 선형 검색(linear search) & 이진 검색(binary search)

선형 검색 (linear search)

- 세트 간격으로 이동하면서 한 번에 하나의 항목을 확인하는 식으로 모든 항목 확인

- 자바스크립트에서 선형 검색 기능을 하는 메서드 => indexOf, includes, find, findIndex

function linearSearch(arr, val) {
	for (let i=0; i<arr.length; i++) {
		if (arr[i] === val) return i;
	}
	return -1;
}

이진 검색 (binray search)

- 확인할 때마다 남은 항목의 절반 제거 (단, 항상 정렬되어 있어야 함)

- 2개의 변수 생성

   -> left idx = 0, right idx = arr.length-1 (left < right 일 때만 실행)

- 구하려는 수와 주어진 배열의 중간 인덱스 값을 비교하여 탐색 항목을 절반씩 줄여감

function binarySearch(arr, val) {
	let left = 0;
	let right = arr.length - 1;
	let mid = Math.floor((left+right)/2);

	while (left <= right) {
		if (val > arr[mid]) {
			left = mid+1;
		} else {
			right = mid-1;
		}
		mid = Math.floor((left+right)/2);
	}
	return arr[mid] === val ? mid : -1;
}