O (log (n)) 미만의 정렬 된 배열에서 검색 실행 시간

Question

O (log (n)) 시간에 정렬 된 숫자 배열에서 숫자를 검색하려면 이진 검색을 사용하고 있습니다. 다음 검색 내 C 함수이다

search(int array[],int size,int search) 
{ 
int first=0; 
int last=size-1; 
int middle = (first+last)/2; 
    while(first <= last) 
    { 
     if (array[middle] < search) 
     first = middle + 1;  
     else if (array[middle] == search) 
     { 
     printf("%d found at location %d.\n", search, middle+1); 
     break; 
     } 
     else 
     last = middle - 1; 

     middle = (first + last)/2; 
    } 
    if (first > last) 
     printf("Not found! %d is not present in the list.\n", search); 
} 

여기

size 배열의 크기 및 search 검색 할 수있다. 위의 프로그램보다 적은 복잡도로 검색을 수행 할 수있는 방법이 있습니까?

Answer 1

예, 해시 테이블을 사용하십시오. 평균적인 경우 더 빠릅니다.