데이터 구조 - 2 분 검색 (python 구현)

최근 에 왕 쟁 선생님 의 을 배우 기 시 작 했 고 정 리 를 통 해 자신의 사고 형식 으로 이 과정 을 기록 했다. 글 은 주로 학습 과정의 기록 으로 삼 았 다.
수업 전 문제: 1000 만 개의 정수 데이터 가 있 고 모든 데이터 가 8 개의 바이트 를 차지한다 고 가정 하면 데이터 구조 와 알고리즘 을 어떻게 설계 하고 특정한 정수 가 이 1000 만 데이터 에 나타 나 는 지 신속하게 판단 하 는 동시에 이 기능 의 메모리 가 100 M 을 초과 하지 않 기 를 바 랍 니 다.
이 문 제 는 2 분 검색 을 도입 했다. 예 를 들 어 2 분 검색 을 이해 했다. 한 배열 이 0 - 99 라 고 가정 하고 요소 23 이 배열 에 있 는 위 치 를 찾 아야 한다.
횟수
추측 범위
중간 수
대비 크기
1
0-99
49
49>23
2
0-48
24
24>23
3
0-23
11
11<23
4
12-23
17
17<23
5
18-23
20
20<23
6
21-23
22
22<23
7
23
√
2 분 의 사상 을 이용 하여 매번 구간 중간 데이터 와 크기 를 비교 하고 검색 구간 의 범 위 를 좁 힌 다. 2 분 의 검색 은 질서 있 는 데이터 집합 을 대상 으로 하고 사상 을 찾 는 것 은 분 치 사상 과 유사 하 다. 매번 구간 의 중간 요소 와 비 교 를 통 해 찾 아야 할 구역 간 을 원래 의 절반 으로 축소 시 켜 찾 아야 할 요 소 를 찾 거나 구간 이 0 으로 축소 된다.
2 점 검색 효율 이 매우 높다.데이터 크기 가 n 이 라 고 가정 하면 검색 할 때마다 데 이 터 는 원래 의 절반 으로 줄 어 들 고, 즉 2 로 나 누 며, 최 악의 경우 검색 구간 이 비어 있 을 때 까지 멈 추 는 것 이다.
찾 은 구간 의 크기 변화:
n n, n / 2 n / 2 n / 2, n / 4 n / 4 n / 4, n / 8 n / 8 n / 8,.
시간 복잡 도 는 O (k) = O (l o g 2 n log 2 {n} log 2 n) 이 므 로 시간 복잡 도 는 O (logn) 이다.
가장 간단 한 2 점 찾기:
가장 간단 한 2 분 검색 은 질서 있 는 배열 에 중복 요소 가 존재 하지 않 습 니 다. 코드:

def binary_search(l,n):
    low = 0
    high = len(l)-1
    while(low<=high):
        mid = low+((high-low)>>1) 
        if n == l[mid]:
            return mid
        elif nl[mid]:
            low = mid+1

다음은 몇 가지 주의해 야 할 점 이 있다.
1. 반복 종료 조건:
low 가 아니 라 low < = high 입 니 다.
2. mid 의 수치:
mid = (low + high) / 2 의 표기 법 에 문제 가 있 습 니 다. low + high 는 넘 칠 수 있 습 니 다. 개선 하 는 방법 은 mid 의 계산 방식 을 low + (high - low) / 2 로 쓰 는 것 입 니 다. 더 최적화 가 필요 하 다 면 2 로 나 누 는 조작 을 비트 연산, 즉 low + (high - low) > > 1 로 바 꿀 수 있 습 니 다. 속도 가 훨씬 빠 릅 니 다.
3. low 와 high 의 업데이트
low = mid + 1, high = mid - 1, low = mid 또는 high = mid 로 직접 쓰 면 사순환 이 발생 합 니 다.
실제로 2 분 검색 은 순환 외 에 재 귀적 으로 도 가능 하 다.

def binary_search(l,n,low,high):   
    while(high>=low):
        mid = ((high-low)>>1)+low
        if l[mid]==n:
            return mid
        elif l[mid]>n:
            return binary_search(l,n,low,mid-1)
        elif l[mid]

이분 검색 응용 장면 의 한계 성
1, 2 분 검색 은 순서 표 구조, 즉 배열 에 의존 합 니 다.
2 분 검색 은 링크 에 적합 하지 않 습 니 다. 주요 원인 은 2 분 검색 알고리즘 이 아래 표 시 된 무 작위 로 요 소 를 방문 해 야 하기 때 문 입 니 다.배열 은 아래 표 시 된 랜 덤 으로 데 이 터 를 방문 하 는 시간 복잡 도 는 O (1) 이 고 링크 는 O (n) 이다.따라서 데 이 터 를 링크 로 저장 하면 2 분 검색 시간 이 복잡 하 다.
2, 2 분 검색 은 질서 있 는 배열 을 대상 으로 합 니 다.
2 분 검색 요구 데 이 터 는 질서 가 있어 야 합 니 다.정렬 시간 복잡 도가 가장 낮은 것 은 O (nlogn) 입 니 다.따라서 정적 인 데 이 터 를 대상 으로 자주 삽입 되 고 삭제 되 지 않 으 면 우 리 는 한 번 의 정렬 을 하고 두 번 의 검색 을 할 수 있다. 이렇게 정렬 하 는 비용 은 균등 하 게 분담 되 고 두 번 의 검색 의 한계 비용 은 비교적 낮 을 것 이다.
3. 데이터 양 이 너무 적어 서 2 점 찾기 에 적합 하지 않 습 니 다.
데이터 의 양 이 매우 적어 서 직접 순 서 를 옮 겨 다 닌 다.데이터 양 이 많 을 때 만 2 분 검색 의 장점 이 비교적 뚜렷 하 다.그러나 데이터 간 의 비교 작업 이 매우 오래 걸 리 면 데이터 의 크기 에 관 계 없 이 2 분 으로 찾 는 것 을 추천 합 니 다.
4. 데이터 양 이 너무 많아 서 2 분 검색 에 적합 하지 않 습 니 다.
2 분 검색 의 바 텀 은 배열 에 의존 해 야 하 며, 배열 은 무 작위 접근 특성 을 지원 하기 위해 메모리 공간 연속 을 요구 하 며 메모리 에 대한 요구 가 까다 롭 습 니 다.따라서 너무 큰 데 이 터 를 배열 로 저장 하 는 것 은 힘 들 고 2 분 으로 찾 을 수 없다.
하나의 사고 문 제 를 보충 하고 프로 그래 밍 은 '하나의 수의 제곱 근 을 구하 고 6 개의 유효 소 수 를 보류 합 니 다' 를 실현 합 니 다.

def sqrt(t):
    low = 0
    high = t
    mid = t/2
    while(abs(t-mid**2)>0.00001): 
        if mid**2>t:
            high = mid
        elif mid**2

네 가지 흔히 볼 수 있 는 이분 찾기 변형 문제
1. 첫 번 째 값 이 주어진 값 과 같은 요 소 를 찾 습 니 다.
이 문 제 는 대응 하 는 값 을 찾 았 을 때 첫 번 째 값 이 아니 라 판단 이 필요 하 다 는 점 이다.만약 mid = 0 이 라면 요 소 는 이미 첫 번 째 값 입 니 다. 즉, 우리 가 찾 은 것 입 니 다.만약 mid 가 0 과 같 지 않 지만 s [mid] 의 이전 요소 s [mid - 1] 가 t 와 같 지 않다 면 s [mid] 는 우리 가 찾 는 첫 번 째 주어진 값 과 같은 요소 입 니 다.s [mid - 1] 도 t 와 같 으 면 high = mid - 1, 찾 아야 할 요 소 는 [low, mid - 1] 에 있 을 것 이기 때 문 입 니 다.

def bin_find(s,t): #             
    low = 0
    high = len(l)-1
    while(high>=low):
        mid = low + ((high-low)>>1)
        if s[mid]t:
            high = mid-1
        elif s[mid]==t:
            if mid==0 or s[mid-1]!=t:
                return mid
            else:
                high = mid-1

2. 마지막 으로 주어진 값 과 같은 요 소 를 찾 습 니 다.
변체 와 유사 하 다

def bin_find(s,t): #              
    low = 0
    high = len(l)-1
    while(high>=low):
        mid = low + ((high-low)>>1)
        if s[mid]t:
            high = mid-1
        elif s[mid]==t:
            if mid==0 or s[mid+1]!=t:
                return mid
            else:
                low = mid+1

3. 주어진 값 보다 큰 첫 번 째 요 소 를 찾 습 니 다.
난이 도 는 s [mid] > = t 에 있 습 니 다.우 리 는 먼저 이 s [mid] 가 우리 가 찾 아야 할 첫 번 째 요소 가 주어진 값 보다 큰 지 살 펴 봐 야 한다.s [mid] 앞 에 원소 가 없 거나 이전 원소 가 찾 으 려 는 t 보다 작 으 면 s [mid] 는 찾 으 려 는 원소 입 니 다.s [mid - 1] 도 찾 으 려 는 t 보다 크 면 찾 으 려 는 요소 가 [low, mid - 1] 사이 에 있 기 때문에 하 이 를 mid - 1 로 업데이트 해 야 합 니 다.

def bin_find(s,t): #               
    low = 0
    high = len(l)-1
    while(high>=low):
        mid = low + ((high-low)>>1)
        if s[mid]=t:
            if mid==0 or s[mid-1]

4. 마지막 으로 주어진 값 보다 작은 요 소 를 찾 습 니 다.
변체 3 과 유사 하 다

def bin_find(s,t): #                
    low = 0
    high = len(l)-1
    while(high>=low):
        mid = low + ((high-low)>>1)
        if s[mid]<=t:
            if mid == 0 or s[mid+1]>t:
                return mid
            else:
                low = mid+1
        elif s[mid]>t:
            high = mid-1

참고 자료: 왕 쟁 의 데이터 구조 와 알고리즘 의 미