Computer Science/Algorithm, Data Structure

자바스크립트 알고리즘 선형 탐색(Linear Search), 이진 탐색(Binaray Search)

Write and Remember 2019. 6. 18. 18:06

모든 자바스크립트 개발자가 알아야 하는 33가지 개념

 

선형 탐색과 이진 탐색 알고리즘에 대해 알아보자.

 

선형 탐색(Linear Search)

 

찾으려고 하는 것을 처음부터 하나하나 탐색을 하고

 

찾으려고 하는 값과 일치하면 멈춘다.

 

function linearSearch(arr, find) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === find)
      return `탐색(find)의 값이 들어있는 배열의 인덱스는 ${i}`;
  }
  return;
}

linearSearch([4, 5, 2, 1, 9], 9) // '탐색(find)의 값이 들어있는 배열의 인덱스는 4'

 

이진 탐색(Binaray Search)

 

시작과 끝의 값을 더하여 2로 나눈 중간값부터 탐색을 한다.

 

탐색하는 값과 중간 값을 비교를 한 후

 

탐색 값이 중간 값보다 작으면 중간 값을 기준으로 좌측 데이터를

 

중간 값보다 크면 중간 값을 기준으로 우측 데이터를 대상으로

 

중간값을 재 설정 후 탐색하는 것을 일치하는 값을 찾을 때 까지 반복한다.

 

아래는 오름차순으로 정렬 된 데이터를 탐색한다.

 

function binarySearch(arr, find) {
  let left = 0; // start
  let right = arr.length - 1; // end

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (arr[mid] === find) {
      return `탐색(find)의 값이 들어있는 배열의 인덱스는 ${mid}`;
    }
    arr[mid] < find ? (left = mid + 1) : (right = mid - 1);
  }

  return;
}

console.log(binarySearch([1, 2, 4, 5], 5)); // '탐색(find)의 값이 들어있는 배열의 인덱스는 3'