algorithm
수색

이진 검색

소개

이진 검색은 나누기 및 정복 검색 알고리즘입니다. 검색 공간에서 요소의 위치를 ​​찾기 위해 O(log n) 시간을 사용합니다. 여기서 n 은 검색 공간의 크기입니다.

이진 검색은 대상 값과 검색 공간의 중간 값을 비교 한 후 각 반복에서 검색 공간을 절반으로 나누어 작동합니다.

이진 검색을 사용하려면 검색 공간을 어떤 방식으로 정렬 (정렬)해야합니다. 중복 된 항목 (비교 함수에 따라 동일하다고 비교되는 항목)은 구분할 수 없지만 Binary Search 속성을 위반하지는 않습니다.

종래에는 비교 함수로보다 작음 (<)을 사용했습니다. a <b이면 true를 반환합니다. a가 b보다 작지 않고 b가 a보다 작지 않으면 a와 b는 동일합니다.

예제 질문

당신은 경제학자입니다, 아주 나쁜 사람입니다. 쌀에 대한 균형 가격 (즉, 공급 = 수요 가격)을 구해야한다.

가격이 높을수록 공급량은 많아지고 수요는 줄어든다는 것을 기억하십시오.

당신의 회사가 시장의 힘을 계산에서 매우 효율적이기 때문에 쌀의 가격이 일정한 가격에 설정되어있는 경우, 당신은 즉시 쌀의 단위로 수요와 공급을 얻을 수있는 p .

상사는 평형 가격을 가능한 한 빨리 원하지만 평형 가격은 최대 10^17 인 양의 정수가 될 수 있으며이 범위에 정확히 1 개의 양의 정수 솔루션이 보장됩니다. 그래서 당신이 그것을 잃기 전에 일을 같이 가라!

getSupply(k) 및 getDemand(k) 함수를 호출 할 수 있습니다.이 함수는 문제에 명시된 작업을 정확하게 수행합니다.

예제 설명

여기서 검색 공간은 1 에서 10^17 입니다. 따라서 선형 탐색은 실행 불가능하다.

그러나 k 가 getSupply(k) 증가하고 getDemand(k) 감소합니다. 따라서 임의의 x > y 에 대해 getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y) . 따라서이 검색 공간은 단순한 것이므로 이진 검색을 사용할 수 있습니다.

다음 psuedocode는 이진 검색의 사용법을 보여줍니다.

high = 100000000000000000     <- Upper bound of search space
low = 1                       <- Lower bound of search space
while high - low > 1
    mid = (high + low) / 2    <- Take the middle value
    supply = getSupply(mid)  
    demand = getDemand(mid)
    if supply > demand        
        high = mid             <- Solution is in lower half of search space
    else if demand > supply
        low = mid              <- Solution is in upper half of search space
    else                       <- supply==demand condition
        return mid             <- Found solution

이 알고리즘은 ~O(log 10^17) 시간에 실행됩니다. 이것은 ~O(log S) 시간까지 일반화 될 수 있는데, 여기서 S는 while 루프의 반복마다 [low : high]에서 [low : mid] 또는 [중간 : 높음] ).

재귀를 사용한 이진 검색의 C 구현

int binsearch(int a[], int x, int low, int high) {
    int mid;

    if (low > high)
      return -1;

    mid = (low + high) / 2;

    if (x == a[mid]) {
        return (mid);
    } else 
    if (x < a[mid]) {
        binsearch(a, x, low, mid - 1);
    } else {
        binsearch(a, x, mid + 1, high);
    }
}

이진 검색 : 정렬 된 숫자

의사 코드를 사용하여 숫자에 대한 이진 검색을 표시하는 것이 가장 쉽습니다.

int array[1000] = { sorted list of numbers };
int N = 100;  // number of entries in search space;
int high, low, mid; // our temporaries
int x; // value to search for

low = 0;
high = N -1;
while(low < high)
{
    mid = (low + high)/2;
    if(array[mid] < x)
        low = mid + 1;
    else
        high = mid;  
}  
if(array[low] == x)
    // found, index is low
else
    // not found

배열 [mid]와 x를 비교하여 일찍 리턴하지 마십시오. 추가 비교는 코드를 느리게 만 진행시킬 수 있습니다. 정수 나누기가 항상 반올림됨에 따라 갇히지 않도록하려면 하나를 낮게 추가해야합니다.

흥미롭게도, 위의 바이너리 버전의 버전을 사용하면 배열에서 x의 가장 작은 항목을 찾을 수 있습니다. 배열에 x의 중복이 포함되어있는 경우 간단히 if 조건에 추가하여 x의 가장 큰 항목을 반환 할 수 있도록 알고리즘을 약간 수정할 수 있습니다.

while(low < high)
    {
        mid = low + ((high - low) / 2);
        if(array[mid] < x || (array[mid] == x && array[mid + 1] == x))
            low = mid + 1;
        else
            high = mid;  
    }

mid = (low + high) / 2 대신 mid = low + ((high - low) / 2) 를 Java 구현과 같은 구현에 사용하면 정말로 큰 입력에 대해 오버플로가 발생합니다.

선형 검색

선형 검색은 간단한 알고리즘입니다. 질의가 발견 될 때까지 항목을 반복하여 선형 알고리즘으로 만듭니다. 복잡성은 O (n)입니다. 여기서 n은 통과 할 항목 수입니다.

왜 O (n)입니까? 최악의 시나리오에서는 모든 n 항목을 검토해야합니다.

책 더미에서 책을 찾는 것과 비교할 수 있습니다. 원하는 책을 찾을 때까지 책을 모두 읽습니다.

아래는 파이썬 구현입니다.

def linear_search(searchable_list, query):
    for x in searchable_list:
        if query == x:
            return True
    return False

linear_search(['apple', 'banana', 'carrot', 'fig', 'garlic'], 'fig') #returns True

라빈 카프

Rabin-Karp 알고리즘 또는 Karp-Rabin 알고리즘은 해싱을 사용하여 텍스트의 패턴 문자열 집합 중 하나를 찾는 문자열 검색 알고리즘입니다. 평균 및 최대 사례 실행 시간은 O (n + m) p)이지만, 최악의 경우의 시간은 O (nm)이며, 여기서 n은 텍스트의 길이이고 m은 패턴의 길이입니다.

문자열 일치를위한 자바의 알고리즘 구현

void RabinfindPattern(String text,String pattern){
    /*
    q a prime number
    p hash value for pattern
    t hash value for text
    d is the number of unique characters in input alphabet
    */
    int d=128;
    int q=100;
    int n=text.length();
    int m=pattern.length();
    int t=0,p=0;
    int h=1;
    int i,j;
//hash value calculating function
    for (i=0;i<m-1;i++)
            h = (h*d)%q;
        for (i=0;i<m;i++){
        p = (d*p + pattern.charAt(i))%q;
        t = (d*t + text.charAt(i))%q;
        }
//search for the pattern 
    for(i=0;i<end-m;i++){
        if(p==t){
//if the hash value matches match them character by character
            for(j=0;j<m;j++)
                if(text.charAt(j+i)!=pattern.charAt(j))
                break;
            if(j==m && i>=start)
                System.out.println("Pattern match found at index "+i);            
        }
        if(i<end-m){
            t =(d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;
            if(t<0)
                t=t+q;
        }    
    }                                
}

해시 값을 계산하는 동안 충돌을 피하기 위해 소수를 나누고 있습니다. 소수로 나눈 후 충돌 가능성은 낮지 만 해시 값이 두 문자열에 대해 동일 할 수있는 기회이므로 여전히 우리는 우리가 적절한 일치를 얻었는지 확인하기 위해 문자로 문자를 검사해야하는 일치를 얻습니다.

t = (d * (t - text.charAt (i) * h) + text.charAt (i + m)) % q;

이것은 패턴의 해쉬 값을 다시 계산하는데, 가장 왼쪽의 문자를 제거한 다음 텍스트에서 새로운 문자를 추가합니다.

선형 검색 (최악, 평균 및 최상의 사례) 분석

우리는 알고리즘을 분석하기 위해 3 가지 경우를 가질 수 있습니다 :

1. 최악의 경우

2. 평균 사례

3. 최상의 사례

   #include <stdio.h>
   
   // Linearly search x in arr[].  If x is present then return the index,
   
   // otherwise return -1
   int search(int arr[], int n, int x)
   {
       int i;
       for (i=0; i<n; i++)
       {
           if (arr[i] == x)
            return i;
       }
   
       return -1;
   }
   

   / * 위 함수를 테스트하는 드라이버 프로그램 * /

   int main()
   {
       int arr[] = {1, 10, 30, 15};
       int x = 30;
       int n = sizeof(arr)/sizeof(arr[0]);
       printf("%d is present at index %d", x, search(arr, n, x));
   
       getchar();
       return 0;
   }   
   

최악의 경우 분석 (일반적으로 완료)

최악의 경우 분석에서 알고리즘의 실행 시간에 대한 상한을 계산합니다. 최대 수의 작업이 실행되는 경우를 알아야합니다. 선형 검색에서 최악의 경우는 검색 할 요소 (위의 코드에서 x)가 배열에 없을 때 발생합니다. x가 없으면 search () 함수는 arr []의 모든 요소와 하나씩 비교합니다. 그러므로, 선형 탐색의 최악의 시간 복잡도는 Θ (n)

평균 사례 분석 (때때로 수행됨)

평균 사례 분석에서 모든 가능한 입력을 가져 와서 모든 입력에 대해 계산 시간을 계산합니다. 계산 된 모든 값을 합계하고 합계를 입력 합계로 나눕니다. 우리는 사례의 분포를 알아야합니다 (또는 예측해야합니다). 선형 검색 문제의 경우 모든 사례가 균일하게 분포되어 있다고 가정합니다 (x가 배열에없는 경우 포함). 그래서 우리는 모든 경우를 더하고 그 합을 (n + 1)로 나눕니다. 다음은 평균 사례 시간 복잡성의 값입니다.

최상의 사례 분석 (가짜)

최상의 사례 분석에서 알고리즘의 실행 시간에 대한 하한을 계산합니다. 우리는 최소한의 작업 횟수가 실행되는 경우를 알아야합니다. 선형 검색 문제에서 x가 첫 번째 위치에있을 때 가장 좋은 경우가 발생합니다. 최상의 경우의 연산 수는 일정하다 (n에 의존하지 않는다). 그러므로 최상의 경우의 시간 복잡도는 Θ (1)입니다. 대부분의 경우 알고리즘을 분석하기 위해 최악의 경우를 분석합니다. 최악의 분석에서 우리는 좋은 정보 인 알고리즘의 실행 시간에 대한 상한을 보장합니다. 실제 사례의 대부분에서 평균 사례 분석을하기가 쉽지 않으며 거의 ​​수행되지 않습니다. 평균 사례 분석에서 가능한 모든 입력의 수학적 분포를 알아야합니다 (또는 예측해야합니다). 최상의 사례 분석은 가짜입니다. 알고리즘의 하한값을 보장한다고해서 최악의 경우 정보가 제공되지 않는 경우 알고리즘 실행에 수 년이 걸릴 수 있습니다.

일부 알고리즘의 경우 모든 경우가 점근 적으로 동일합니다. 즉, 최악의 경우와 최상의 경우는 없습니다. 예 : 병합 정렬. Merge Sort는 모든 경우에 Θ (nLogn) 연산을 수행합니다. 다른 정렬 알고리즘의 대부분은 최악의 경우와 가장 좋은 경우가 있습니다. 예를 들어, 빠른 정렬 (피벗이 모서리 요소로 선택됨)의 일반적인 구현에서 입력 배열이 이미 정렬 된 경우 최악이 발생하며 피벗 요소가 항상 두 반쪽으로 배열을 나눌 때 가장 좋습니다. 삽입 정렬의 경우 배열이 역순으로 정렬 될 때 최악의 경우가 발생하고 배열이 출력과 동일한 순서로 정렬 될 때 최상의 경우가 발생합니다.