[CS] 선형 검색, 이진 검색

/* 모두를 위한 컴퓨터 과학(CS50 2019) 정리본입니다. */

요새 면접준비와 개인 프로젝트 + 영어공부 때문에 CS 강의를 못 들었다...
어제 본 면접에서 연결리스트 질문이 있었는데, '모두를 위한 컴퓨터 과학(CS50 2019)'를 끝까지 들었으면 답변할 수 있었을 것 같았다. 빨리 다 듣고 싶다 ㅜ 그리고 이제부터 진짜 중요한 알고리즘 수업이라서 제대로 정리해서 이 자료들을 계속 볼 예정이다.

만약 어떤 값이 배열 안에 속해 있는지 찾아보기(ex. 락커 안에 50이 있는지 확인) 위해서는 배열이 정렬되어있는지 여부에 따라 선형 검색과 이진 검색 방법을 사용할 수 있다.

1. 선형 검색(Linear Search)

---

락커를 첫번째부터 열어서 50을 찾는 방법이다. CS적으로는 '배열의 index를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지 검사'하는 방법이다. 배열에서 검색하는 방법 중 가장 생각하기 쉬운 방법인 것 같다.

// psudo
For i from 0 to n-1

	If i'th element is 50
    	return true

Return false

JavaScript로 구현해보기

const arr = [35, 20, 25, 45, 10, 50, 5, 30, 15, 40];
for (let i = 0; i < arr.length; i++) {
	if (arr[i] === 50) {
    console.log("true")
  }
}

위 코드에서 else { console.log("false") }를 해주면 true 1개와 false 9개가 뜬다. 50이 들어있는지만 판별하면 된다고 생각해서 else는 안써줬다.

2. 이진 검색(Binary Search)

---

배열이 정렬되어 있는 상태라면, 중간 index부터 시작하여 찾고자 하는 값과 비교 후 그보다 작은 index 또는 큰 index로 이동을 반복한다. 이것이 이진 검색이다.

이진 검색은 전에 전화번호부에서 가장 효율적으로 'Mike Smith'찾기에서 다뤘던 내용과 같다.
'Mike Smith 찾기' 포스팅 바로가기

강의에서는 no items의 경우를 제일 나중에 고려했으면서 맨 위에 위치시켰다. 그리고 끝까지 돌아야 없는지 알 수 있는거니까 else if 로 처리해야 되지 않을까..?

// psudo
If no items
	return false

If middle Item is 50
	return true
    
Else if 50 < middle item
	search left half
    
Else if 50 > middle item
	search right half

JavaScript로 구현해보기

const arr = [35, 20, 25, 45, 10, 50, 5, 30, 15, 40];
const sortedArr = arr.sort((a, b) => a - b);
const target = 50;

function binarySearch(target, sortedArr) {
  let low = 0;
  let high = sortedArr.length - 1;
  let mid = Math.floor((low + high) / 2);
  
  while (target !== sortedArr[mid]) {
    if (target < sortedArr[mid]) {
      high = mid - 1;
      mid = Math.floor((low + high) / 2);
    } else {
      low = mid + 1;
      mid = Math.floor((low + high) / 2);
    }
  }
  return sortedArr[mid]
}

binarySearch(target, sortedArr); // 50

이미 정렬된 배열을 가지고 처리해야해서 sort를 썼다. Mike Smith때는 자바스크립트 코드로 안만들어 봤는데, 이진 검색을 코드로 만들어보니까 이렇게 생겼다. 참고로 Math.floor() 함수는 주어진 숫자와 같거나 작은 정수 중에서 가장 큰 수를 반환한다.