선형 탐색

선형 탐색이란 찾고자 하는 값을 요소마다 모두 탐색하며 찾는 방법이다.
선형 탐색은 아래와 같이 구현할 수 있다.

function linearSearch(arr, val) {
	for(let x of arr) {
		if(x === val) return true;
      	else return false;
    }
}

linearSearch([1,2,3,4,5], 3) // true

선형 탐색을 사용하면 입력값이 커짐에 따라 마다 반복 횟수도 비례해서 늘어나기 때문에
시간 복잡도는 O(n)이 된다.

이진 탐색

이진 탐색은 선형 탐색 보다 효율적으로 값을 찾을 수 있다.
시작인덱스, 중간인덱스, 마지막인덱스를 가리키는 변수를 설정하여,
찾고자 하는 값과 중간인덱스를 비교하며 탐색 범위를 축소해나가는 알고리즘이다.

이진 탐색을 코드로 구현하면 아래와 같다.

function binarySearch(arr, val) {
	let start = 0;
  	let end = arr.length - 1;
  
  	while(start <= end) {
	  	let mid = Math.floor((start + end) / 2);
		if(arr[mid] === val) return true;
      	else if(arr[mid] < val) start = mid + 1;
      	else if(arr[mid] > val) end = mid - 1;
    }
  
  	return false;
}

1. 시작인덱스, 마지막인덱스를 가리키는 변수를 선언한다.
2. while문으로 반복하고, 종료 조건을 start <= end 로 지정한다.
3. 반복문이 실행될 때 마다 mid인덱스가 새로 설정될 수 있도록 한다.
4. 만약 arr[mid]가 찾고자 하는 값보다 작다면, start인덱스를 mid + 1로 바꾼다.
5. 만약 arr[mid]가 찾고자 하는 값보다 크다면, end인덱스를 mid - 1로 바꾼다.
6. 이렇게 범위를 좁혀가며 탐색하다가 arr[mid]와 찾고자 하는 값과 같으면 true를 리턴하고,
   start인덱스가 end인덱스보다 커지게 되면 반복문이 종료되며 false를 리턴하게 된다.
   (찾고자 하는 값이 없다는 뜻)

이진 탐색을 사용하면 입력값이 늘어나도 반복 횟수가 대략 절반씩 줄어들기때문에 시간 복잡도는 O(log n)이 된다.

이진 탐색은 정렬된 배열 에서만 사용이 가능하니, 만약 정렬되지 않은 배열에서 탐색을 해야 할 때는 다른 선택지를 고려해보자.