알고리즘: 선형 검색 및 이진 검색

논리와 데이터 구조의 기본 개념을 소개하는 간단한 알고리즘도 있고, 더 복잡한 것을 목표로 하는 알고리즘도 있습니다.

검색 알고리즘은 전화번호부에서 연락처를 찾거나 컴퓨터에서 파일을 찾는 등 대량의 데이터에서 정보를 찾는 데 유용합니다.

이러한 의미에서 이 글은 선형 검색 및 이진 검색 알고리즘과 관련된 개념을 소개하는 것을 목표로 합니다.

1. 선형검색

• 목록을 순차적으로 스캔하여 요소를 찾습니다
• 예를 들어 배열에서 특정 숫자를 검색하는 것이 있습니다

선형 검색 알고리즘은 서술문에서 정수 배열과 검색 참조가 될 값(target이라고 함)이 입력 매개변수가 된다는 의미입니다. 이런 의미에서 이러한 값을 받는 함수가 있으며, 이를 통해 먼저 for를 사용하여 기존 위치의 최대 크기까지 이 배열의 각 위치를 통과한 다음 if를 사용하여 각 위치가 목표와 동일한 값을 가지고 있는지 여부에 대한 검사가 조건화됩니다. 값이 발견되면 함수는 해당 위치의 인덱스를 반환하거나 찾을 수 없는 사례를 나타내는 -1을 반환합니다.

JavaScript를 사용하는 예는 다음과 같습니다.

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

따라서 이 알고리즘은 요소가 있는 위치 또는 인덱스를 반환하는 것을 목표로 하며, 심지어 요소를 찾은 후 계속할 필요 없이 단순히 첫 번째 해당 요소를 찾는 것을 목표로 합니다. 이 동작은 조건이 만족되면 요소 인덱스로 반환을 실행하고 그 후 루프를 종료하여 함수를 종료하는 알고리즘의 명령으로 인해 발생합니다.

이 알고리즘은 목록이 작거나 순서가 지정되지 않은 시나리오에서 유용할 수 있습니다. 각 요소를 순회해야 하며 추가 메모리 사용량이 없습니다.

2. 이진 검색

• 순서가 지정된 목록을 스크롤하여 요소를 찾으세요
• 예를 들어 배열에서 특정 숫자를 검색하는 경우를 들 수 있습니다

이진 검색 알고리즘은 정렬된 배열에서 주어진 값을 찾는 보다 효율적인 형태의 알고리즘입니다. 이는 검색 범위를 반복적으로 절반으로 나누는 방식으로 작동하므로 대규모 데이터세트에 대한 선형 검색보다 훨씬 빠릅니다. 이진 검색의 복잡성은 O(log n)인 반면 선형 검색의 복잡성은 O(n)입니다.

JavaScript의 예는 다음과 같습니다.

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

로직은 두 개의 포인터로 시작하는 것으로 구성됩니다. 하나는 배열의 시작(낮음)에 있고 다른 하나는 끝(높음)에 있습니다. 따라서 중간 인덱스가 계산됩니다. const middle = Math.floor((low high) / 2). 이를 통해 각 단계에서 중간 요소가 대상과 비교됩니다. 중간 요소가 대상과 같으면 인덱스가 반환됩니다. 그러나 중간 요소가 대상 요소보다 작거나 중간 < target은 가장 작은 숫자를 버리고 시작을 low = middle 1로 배치하는 것을 의미합니다. 결과적으로 중간 요소가 target middle > target, 목표보다 큰 숫자는 버려지고 최종 인덱스를 high = middle - 1로 조정됩니다. 이 프로세스는 목표를 찾을 때까지 또는 범위가 유효하지 않게 될 때까지 반복됩니다. low > 높습니다.

이진 검색은 알파벳 사전이나 순서가 지정된 날짜 집합과 같이 순서가 지정된 데이터를 찾을 때 효율적일 수 있습니다. 각 반복에서 문제를 더 작은 하위 문제로 나눌 수 있으므로 더 빠르고 효율적인 경향이 있습니다.

따라서 선형 검색은 간단하고 작은 목록에서 작동하는 것으로 이해됩니다. 이진 검색은 훨씬 더 효율적이지만 정렬된 데이터가 필요합니다.

다양한 알고리즘의 작동 방식과 사용 맥락을 이해하는 것은 효율적인 계산 솔루션을 구축하기 위한 중요한 단계입니다. 이러한 방법을 구현하고 분석하고 이러한 전략이 실제 문제를 해결하기 위해 어떻게 적용될 수 있는지 알아보세요. =)

위 내용은 알고리즘: 선형 검색 및 이진 검색의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!