Search Algorithm

1️⃣ Search Algorithm ?

Search Algorithm이란 말그대로 찾는 방법이다. 어떠한 배열이 주어지고 찾고자 하는 값이 있다면 주어진배열내에 찾고자하는 값이 존재하는지 확인을 하는 것이다. JS의 Array객체에는 Search메소드가 내장되어 있다. indexOf, includes, find, findIndex 등등이 존재한다.

2️⃣ Linear Search(선형검색) ?

1. 배열과 값을 입력받는다.
2. 배열을 순회하며 현재요소와 값이 같은지 확인한다.
3. 주어진 값과 일치하는 요소가 존재한다면 true, index 등을 리턴해준다.
4. 주어진 값과 일치하는 요소가 존재하지않는다면 false 또는 -1 등을 리턴한다.

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

선형검색은 위와같다. 모든요소를 순회하며 값을 찾는 것이다. 그러므로 O(N)시간 복잡도를 가지고있다. (위에 언급한 Array객체의 메소드들은 여기에 속한다)

3️⃣ Binary Search(이진검색) ?

이진검색은 앞선 선형검색보다 훨씬 빠른 검색방법이다. 요소와 값을 비교한 후 대소비교결과에 따라 나머지 요소의 절반을 제거할 수 있다.(이진 검색은 정렬된 배열에서만 사용할 수 있다) 간단히 이해하자면 Up & Down게임을 생각하면 되겠다.

1. 정렬된 배열과 값을 입력받는다.
2. 배열의 시작 부분에 왼쪽 포인터를 만들고 배열의 끝 부분에 오른쪽 포인터를 만든다.
3. 왼쪽 포인터가 오른쪽 포인터보다 작거나 같을때까지 아래를 실행한다
   3 - 1 중간 포인터만들기
   3 - 2 중간 포인터와 값이 일치한다면 index 또는 true를 리턴한다.
   3 - 3 중간 포인터의 값이 찾는 값보다 작다면 찾고자하는 값은 중간포인터의 오른쪽에 존재한다
   3 - 4 중간 포인터의 값이 찾는 값보다 작다면 찾고자하는 값은 중간포인터의 오른쪽에 존재한다
4. 값을 찾지 못하면 -1 또는 false를 리턴한다.

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

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

return -1;
}