Untitled

알고리즘 : 어떤 과제를 완수하는 명령어 집합

컴퓨팅 관점에서 알고리즘은 특정 과제를 달성하기 위해 컴퓨터에 제공되는 명령어 집합을 뜻한다. 즉, 어떤 코드를 작성하든 컴퓨터가 따르고 실행할 알고리즘을 만드는 것

2-1 정렬된 배열

정렬된 배열은 값이 항상 순서대로 있어야 한는 배열이다. 즉, 값을 추가 할 때마다 적절한 셀에 넣어 배열의 값을 정렬된 상태로 유지한다.

정렬된 배열에 삽입할 때는 항상 실제 삽입 전에 검색을 먼저 수행해서 삽입할 오바른 위치를 정해야 된다. 전형적인 배열과 정렬된 배열의 성능 차이 중 하나.

전형적인 배열보다는 덜 효율적이지만, 정렬된 배열의 강력함은 검색 연산에서 드러난다.

2-2 정렬된 배열의 검색

정렬된 배열에서는 값이 배열에 들어있지 않을 때 검색을 더 빨리 멈출 수 있다.

const linerSearch = (array, serachValue) => {
	// 배열의 모든 원소를 순회한다
	for(let i = 0; i < array.length; i++) {
		if(array[i] === searchValue){
		// 원하는 값을 찾으면 그 인덱스를 반환
		return i;
		}
		else if(array[i] > searchValue){
			// 찾고 있던 값보다 큰 원소에 도달하면 루프를 일찍 종료한다
			break;
		}
	}
	// 배열에서 값을 찾지 못하면 null을 반환
	return null;
}

linearSearch([3, 17, 75, 80, 202], 22 )

선형 검색은 특정 상황에서 전형적인 배열보다 정렬된 배열에서 단계 수가 더 적게 걸린다. 하지만 찾으려는 값이 배열의 마지막 값이거나 마지막 값보다 크면 마찬가지로 모든 셀을 검색해야 끝난다.

하지만 정렬된 배열이 전형적인 배열보다 다른 검색 알고리즘을 쓸 수 있다.

이러한 알고리즘을 이진 검색이라 부르며 선형 검색보다 훨씬 빠르다.

2-3 이진 검색

이진 검색은 계속해서 가운데 셀을 골라 남은 수 중 반을 제거해 나가는 방법이다.

이진 검색은 정렬된 배열에만 쓸 수 있다. 전형적인 배열은 값의 순서가 뒤죽박죽이어서 주어진 값의 왼족에서 찾을지 오른쪽에서 찾을지 절대 알 수 없다.

2-3-1 코드 구현: 이진 검색


const binarySearch = (array, searchValue) => {
	// 먼저 찾으려는 값이 있을 수 있는 상한선과 하한선을 정한다
	// 최초의 상한선은 배열의 첫 번째 값, 하한선은 마지막 값이다.
	let lowerBound = 0;
	let upperBound = array.length - 1;
	
	// 상한선과 하한선 사이의 가운데 값을 계속해서 확인하는 루프를 시작한다
	while(lowerBound <= upperBound){
		// 상한선과 하한선 사이에 중간 지점을 찾는다
		// 책의 코드는 루비에서 결과값이 정수가 아닐 때 가장 가까운 정수로 올림한다고 했으므로 결과값을 가장 가까운 정수로 올림한다.
		const midPoint = Math.ceil((upperBound + lowerBound) / 2);
		
		// 중간 지점의 값을 확인한다
		const valueAtMidPoint = array[midPoint]
	
		// 중간 지점의 값이 찾고 있던 값이면 검색을 끝낸다
		// 아니면 더 클지 작을지 추측한 바에 따라 상한선 혹은 하한선을 바꾼다
		if(searchValue === valueAtMidPint){
			return midPoint;
		} else if (searchValue < valueAtMidPoint)[
			upperBound = midPoint - 1;
		} else if (searchValue > valueAtMidPoint){
			lowerBound = midPoint + 1;
		}
	}
	// 상한선과 하한선이 같아질 때까지 경계값을 줄였다면 찾고 있는 이 배열에 없다는 의미
	return null;
};
binarySearch([3, 17, 75, 80, 202], 22);