1. 알고리즘(Algorithm)

• 문제를 해결하는 방법
• 특정 종류의 문제를 풀기 위한 일련의 연산을 제공하는 유한한 규칙의 집합

1) 특성

(1) 입력 (Input)

: 0이나 그 이상의 입력값을 가진다.

(2) 출력 (Output)

: 하나 혹은 그 이상의 출력값을 가진다.

(3) 명확성 (Definiteness)

: 각 단계는 무엇을 하기 위한 것인지 명확해야한다.

(4) 유한성

: 각 단계들은 유한한 횟수를 거친 후 종료되어야한다.

(5) 효과성

: 시간적, 공간적 효율성을 가져야한다.

2. 탐색 알고리즘 (Search Algorithm)

• 탐색 알고리즘 또는 검색 알고리즘이라고 불린다. 둘 다 같은 말.
• 정렬 혹은 비정렬된 리스트에서 어떤 대상의 존재나 위치를 찾는 알고리즘이다.
• 대표적으로 선형탐색(순차탐색), 이진탐색, 해시탐색이 있다.

1) 선형탐색

• 선형탐색(Linear Search) 또는 순차탐색(Sequential Search)이라 불린다.
• 배열, 링크드리스트 등 데이터가 모인 집합의 처음부터 끝깢지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘
• [1,2,3,4,5] 와 같은 배열에서 4을 찾아내기 위해 1부터 4까지 비교해야하기 때문에 4번의 탐색을 하게 된다.
  => 데이터의 양이 많아지면 검색에 소요되는 시간도 비례해서 길어진다.
• 처음부터 찾을 때까지 비교하기 때문에 비효율적이다. 데이터가 100만개 있으면 100만개 다 탐색해야할 수도 있다.
• 시간복잡도 : O(n) => n번만큼의 시간이 걸리기 때문이다.

const arr = [1,2,3,4,5,6,7,8,9,10];

const linearSearch = (arr, target) => {
  for(let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return console.log(i, arr[i]);
    } 
  }
  return console.log('i does not exist.')
};

linearSearch(arr, 5); // 4 5
linearSearch(arr, 11); // 'i does not exist.'

2) 이진탐색

• 이진탐색/이진검색/이분검색이라 불린다.
• 데이터가 반드시 정렬(sort)되어있어야 한다.
• 데이터의 중간값부터 탐색하며 탐색 범위를 반으로 줄이면서 탐색하는 방법이다.
• 트리구조에서 자주 쓰인다.
• 데이터의 중간값부터 검색을 하기 때문에 처리속도가 빠르다.
• 시간복잡도 : O(logn)

const arr = [1,2,3,4,5,6,7,8,9,10];

const binarySearch = (arr, target) => {
  let min = 0;
  let max = arr.length -1;
 
 // min이 max보다 작거나 같을 때까지 while문 실행
 while(min <= max) {
  let mid = Math.floor((min + max)/2);
   if (arr[mid] === target) {
     return console.log(mid, arr[mid]);
   } else if (arr[mid] < target) {
     // 배열 중앙값의 오른쪽에서 다시 중앙값을 탐색하기 위해
     min = mid+1;
   } else {
     // 배열 중앙값의 왼쪽에서 다시 중앙값을 탐색하기 위해
     max = mid-1;
   }
 }
return console.log('Target dose not exist');
}

binarySearch(arr, 6); // 5 6
binarySearch(arr, 3); // 2 3
binarySearch(arr, 11); // 'Target dose not exist'

---

• for문 : 반복이 몇 번 있는지 알 때 사용
• while문 : 반복이 몇 번 있는지 모를때 사용