이진 검색 개념

Do you want to understand binary search? Read this article, I have discussed binary search problems in JavaScript.

이진 검색 개념

지켜봐 주세요. 이것은 내가 본 최고의 이진 검색 비디오입니다. 다음으로 그가 강의에 참석하면서 모든 문제를 해결하십시오.

이진 검색은 주어진 정렬된 배열에서 수행할 수 있으며 다음을 수행하는 데 사용됩니다.

번호 검색

주어진 조건으로 숫자를 검색합니다.

제곱, 제곱근 등과 같은 실제 값 찾기

이진 검색 문제에 대한 엄지손가락 규칙

Divide your array in set of TRUE and FALSE values then find the First occurrence of TRUE or the last occurrence of TRUE. Binary Search Array should be partially false and partially true. We need to find the boundary between them.

이진 검색 알고리즘

function binarySearch(array, data) {
  let low = 0;
  let high = array.length - 1;

  while (low <= high) {
    let mid = low + Math.floor((high - low) / 2);
    if (data === array[mid]) return mid;
    else if (data < array[mid]) high = mid - 1;
    else low = mid + 1;
  }

  return -1;
}

Binary Search on Sorted Array Algorithm에서 Rupesh Tiwari(@roopkt)의 펜CodePen을 참조하십시오.

JavaScript의 이진 검색 문제

그의 강의를 보는 동안 나는 모든 문제 해결을 JavaScript로 변환했습니다.

주어진 숫자가 SQUARE인지 찾기

의문

function isSquare(x) {}
describe('IsSquare', () => {
  it('should work correctly #1', () => {
    expect(isSquare(16)).toBeTruthy();
  });
  it('should work correctly #2', () => {
    expect(isSquare(6570204424081)).toBeFalsy();
  });
});

대답

function isSquare(x) {
  // For Array the maximum length is 2GB-1 (2^32-1)
  if (x >= Math.pow(2, 32)) return false;
  const array = Array.from(Array(Math.floor(x / 2)).keys());
  let low = 0;
  let high = array.length - 1;
  let mid;
  let square;
  while (low <= high) {
    mid = low + Math.floor((high - low) / 2);
    square = Math.pow(array[mid], 2);
    if (x === square) return true;
    else if (x < square) high = mid - 1;
    else low = mid + 1;
  }

  return false;
}

@roopkt에서 Rupesh Tiwari(CodePen)의 펜을 참조하십시오.

주어진 숫자의 제곱근 찾기

의문

function sqrt(x) {}

describe('Find Square Root of x', () => {
  it('should work correctly #1', () => {
    expect(sqrt(4)).toBe(2);
  });
  it('should work correctly #2', () => {
    expect(sqrt(36)).toBe(6);
  });
});

대답

function sqrt(x) {
  var array = Array.from(Array(x).keys());
  let low = 0;
  let high = array.length - 1;
  while (low <= high) {
    let mid = low + Math.floor((high - low) / 2);
    let square = array[mid] * array[mid];
    if (square === x) {
      return mid;
    } else if (square > x) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
}

@roopkt에서 Rupesh Tiwari(CodePen)의 펜을 참조하십시오.

주어진 숫자보다 큰 첫 번째 값 찾기

의문

function findFirstValue(array, data) {}

describe('Find First Value >= x in sorted array', () => {
  it('should work correctly #1', () => {
    expect(findFirstValue([2, 3, 5, 6, 8, 10, 12], 4)).toBe(5);
  });
});

대답

function findFirstValue(array, data) {
  let low = 0;
  let high = array.length - 1;
  let mid;
  let result = -1;
  while (low <= high) {
    mid = low + Math.floor((high - low) / 2);
    if (array[mid] >= data) {
      result = array[mid];
      high = mid - 1; // since I need first occurrence so keep searching in the left sorted half of the array.
    } else low = mid + 1;
  }

  return result;
}

Find First Value greater than given number에서 Rupesh Tiwari(@roopkt)의 펜CodePen을 참조하십시오.

순환 정렬된 배열에서 최소값 찾기

순환 정렬 배열의 피벗 번호이기도 합니다. 피벗 요소를 찾으면 인덱스 값을 통해 배열이 이동/회전된 횟수를 알 수 있습니다. 피벗 요소의 인덱스는 개수 또는 회전도 제공합니다.

의문

function findMinInCircularlySortedArray(array) {}

describe('Find Min in Circularly Sorted Array', () => {
  it('should work correctly #1', () => {
    expect(findMinInCircularlySortedArray([11, 12, 15, 18, 2, 5, 6, 8])).toBe(
      2
    );
  });
  it('should work correctly #2', () => {
    expect(findMinInCircularlySortedArray([6, 7, 9, 15, 19, 2, 3])).toBe(2);
  });
});

대답

function findMinInCircularlySortedArray(array) {
  let low = 0;
  let length = array.length;
  let high = length - 1;
  let mid;
  let result = -1;
  while (low <= high) {
    mid = low + Math.floor((high - low) / 2);
    if (array[mid] <= array[length - 1]) {
      result = array[mid];
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  return result;
}

증가하는 감소하는 배열에서 최대 수 찾기

의문

function findMaximumInIncreasingDecreasingArray(array) {}

describe('find Maximum In Increasing and Decreasing Array', () => {
  it('should work correctly #1', () => {
    expect(
      findMaximumInIncreasingDecreasingArray([
        2,
        3,
        4,
        6,
        9,
        12,
        11,
        8,
        6,
        4,
        1,
      ])
    ).toBe(12);
  });
});

대답

function findMaximumInIncreasingDecreasingArray(array) {
  let low = 0;
  let high = array.length - 1;
  let mid;
  let answer = -1;
  while (low <= high) {
    mid = low + Math.floor((high - low) / 2);
    if (array[mid] >= array[mid - 1] || mid === 0) {
      answer = array[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return answer;
}

Find Maximum in increasing decreasing array에서 Rupesh Tiwari(@roopkt)의 펜CodePen을 참조하십시오.

모든 이진 검색 기본 문제

다음은 see all binary search basic questions에 대한 링크입니다.

참조

제 글을 끝까지 읽어주셔서 감사합니다. 오늘 특별한 것을 배웠기를 바랍니다. 이 기사가 마음에 드셨다면 친구들과 공유해 주시고 저와 공유할 제안이나 생각이 있으시면 댓글 상자에 적어주세요.

풀 스택 개발자 되기 💻

나는 Fullstack Master에서 가르칩니다. 소프트웨어 개발자가 되고 새로운 소프트웨어 엔지니어 또는 수석 개발자/설계자로 캐리어를 성장시키려는 경우. 전체 스택 개발 교육 프로그램에 가입하는 것을 고려하십시오. 많은 코딩 실습을 통해 Angular, RxJS, JavaScript, 시스템 아키텍처 등을 배우게 됩니다. All-Access Monthly 멤버십 플랜이 있으며 모든 비디오 코스, 슬라이드, 소스 코드 다운로드 및 월간 화상 통화에 무제한으로 액세스할 수 있습니다.

현재 및 미래의 Angular, node.js 및 관련 과정에 액세스하려면 All-Access Membership PRO plan을 구독하십시오.

PRO 플랜의 모든 것을 얻으려면 All-Access Membership ELITE plan에 가입하세요. 또한 Rupesh와의 월별 라이브 Q&A 화상 통화에 액세스할 수 있으며 의심/질문을 하고 더 많은 도움, 팁 및 요령을 얻을 수 있습니다.

Your bright future is awaiting for you so visit today FullstackMaster and allow me to help you to board on your dream software company as a new Software Developer, Architect or Lead Engineer role.

💖 나에게 👋라고 말해!
루페시 티와리
Fullstack Master의 설립자
이메일: [email protected]
웹사이트: www.rupeshtiwari.com | www.fullstackmaster.net