ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 자바스크립트 알고리즘 선형 탐색(Linear Search), 이진 탐색(Binaray Search)
    Computer Science/Algorithm, Data Structure 2019.06.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}`
        }
        if (arr[mid] < find) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
      return;
    }
    
    binarySearch([1, 2, 4, 5], 5) // '탐색(find)의 값이 들어있는 배열의 인덱스는 3'

     

    소수점 버리는 함수

     

    Math.floor() 

     

    함수는 주어진 숫자와 같거나 작은 정수 중에서 가장 큰 수를 반환한다.

    댓글 0