이진 검색 || 파이썬 || 데이터 구조 및 알고리즘

이진 검색

이진 검색은 검색 공간을 반복적으로 반으로 나누는 알고리즘입니다. 이 검색 기술은 분할 정복 전략을 따릅니다. 검색 공간은 반복할 때마다 항상 절반으로 줄어듭니다. 결과적으로 O(log(n))의 시간 복잡도가 발생합니다. 여기서 n은 요소 수입니다.

조건: 배열은 정렬되어야 하지만 단조 증가 또는 감소를 찾아야 하는 단조 함수에 적용될 수도 있습니다.

로그 시간으로 검색 공간을 좁혀야 할 때 효과적입니다.

왼쪽과 오른쪽 두 개의 포인터를 사용합니다. 왼쪽과 오른쪽의 평균을 구하여 중간 요소를 찾습니다.

이제 조건에 따라 왼쪽 포인터와 오른쪽 포인터를 어디로 움직여야 하는지 확인해 보겠습니다.

문제를 해결하려면 주로 세 가지 단계가 필요합니다.

1. 전처리: 입력값이 정렬되지 않은 경우 정렬합니다.
2. 이진 검색: 두 개의 포인터를 사용하여 중앙을 찾아 검색 공간을 나눈 ​​다음 그에 따라 올바른 절반을 선택합니다.
3. 후처리: 출력을 결정합니다.

이진 검색 알고리즘의 장점 - 이진 검색은 각 요소를 하나씩 확인하는 대신 매번 배열을 반으로 자르므로 대용량 데이터에 대한 선형 검색보다 빠릅니다. 이를 통해 더 빠르고 효율적으로 작업할 수 있습니다.

제한 사항: 이진 검색은 정렬된 배열에서만 작동하므로 정렬에 추가 시간이 걸리므로 정렬되지 않은 작은 배열에는 효율적이지 않습니다. 또한 소규모 메모리 내 검색에 대한 선형 검색은 작동하지 않습니다.

응용 프로그램: O(log(n)) 시간 복잡도로 정렬된 배열에서 요소를 검색하는 데 사용되며 배열에서 가장 작거나 큰 요소를 찾는 데에도 사용할 수 있습니다.

기본 이진 검색 코드 -

암호

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1

33. 회전 정렬 배열에서 검색
가능한 회전 후의 배열 nums와 정수 대상이 주어지면 대상이 nums에 있으면 대상의 인덱스를 반환하고, nums에 없으면 -1을 반환합니다.
런타임 복잡도가 O(log n)인 알고리즘을 작성해야 합니다.
예시 1:
입력: 숫자 = [4,5,6,7,0,1,2], 대상 = 0
출력: 4

예 2:
입력: 숫자 = [4,5,6,7,0,1,2], 대상 = 3
출력: -1

예 3:
입력: 숫자 = [1], 대상 = 0
출력: -1

암호

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1

1. 왼쪽과 오른쪽의 두 포인터를 사용하여 겹칠 때까지 반복합니다.
2. 중간 요소를 찾아보세요.
3. 배열은 정렬되었으나 회전되기 때문에 단순히 왼쪽이나 오른쪽 요소를 중간 요소와 비교할 수는 없습니다.
4. 먼저 중간 포인터와 왼쪽 또는 오른쪽 포인터를 비교하여 왼쪽 또는 오른쪽으로 정렬된 부분을 결정합니다.
5. 이러한 결론에 따라 포인터를 적절하게 조정하세요.

시간 복잡도 - O(log(n)) 각 반복마다 검색 공간이 절반으로 나누어집니다.
공간 복잡도 - O(1)

단조 증가

162. 피크 요소 찾기

피크 요소는 이웃 요소보다 엄격하게 더 큰 요소입니다.
0부터 인덱스가 지정된 정수 배열 nums가 주어지면 피크 요소를 찾고 해당 인덱스를 반환합니다. 배열에 여러 피크가 포함된 경우 피크 중 하나에 대한 인덱스를 반환합니다.
nums[-1] = nums[n] = -무한이라고 상상할 수 있습니다. 즉, 요소는 항상 배열 외부에 있는 이웃보다 더 큰 것으로 간주됩니다.
O(log n) 시간에 실행되는 알고리즘을 작성해야 합니다.

예 1:
입력: 숫자 = [1,2,3,1]
출력: 2
설명: 3은 피크 요소이며 함수는 인덱스 번호 2를 반환해야 합니다.
예시 2:
입력: 숫자 = [1,2,1,3,5,6,4]
출력: 5
설명: 함수는 피크 요소가 2인 인덱스 번호 1 또는 피크 요소가 6인 인덱스 번호 5를 반환할 수 있습니다.

암호

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1

        while left <= right:

            mid = (left + right)//2
            print(f'left is {left},right is {right} and mid is {mid}')
            if nums[mid]==target:
                return mid

            if nums[mid] >= nums[left]:
                # if nums[mid]< target and target >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid -1
                else:
                    left = mid +1
            else:
                # if nums[mid] < target and target <= nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid +1
                else:
                    right = mid - 1

        return -1

1. 이런 유형의 문제에서는 중앙의 왼쪽 요소와 오른쪽 요소를 비교하여 정점을 확인해야 합니다.
2. 이는 그래프가 상승 추세인지 하락 추세인지 판단하는 데 도움이 됩니다.
3. 최대값을 찾으려면 위쪽 기울기를 검색하고 올바른 부분 공간을 탐색하세요.
4. 최소값을 찾으려면 왼쪽 하위 공간을 검색하세요

시간 복잡도 - O(log(n)) 각 반복마다 검색 공간이 절반으로 나누어집니다.
공간 복잡도 - O(1)

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