[Algorithm] 특정 대상을 검색하는 효율적인 방법

http://stackoverflow.com/questions/34481582/efficient-way-to-search-an-element

Q: 특정 대상을 검색하는 효율적인 방법

최근에 면접을 봤는데, "검색"에 대한 질문을 받았습니다.

문제는 아래와 같습니다.

정수의 배열 (양의 정수)이 있다고 가정합니다. 각각의 요소는 옆에 붙어있는 요소와 비교할 때, +1 이거나 -1입니다.

예:

array = [4,5,6,5,4,3,2,3,4,5,6,7,8]

이제 7을 찾아서 그 위치를 반환하세요.

저는 이렇게 답했습니다.

배열의 값을 임시배열에 저장하고, 한 번 정렬합니다. 그리고 바이너리 서치를 수행합니다.

만약 해당 요소가 발견되면, 그 값과 위치를 리턴합니다.

(만약 해당 요소가 두 번 발견된다면, 처음 발견한 것의 위치를 반환합니다)

하지만 그들은 이 대답에 만족하지 못한 것 같았습니다.

왜 이것이 올바른 대답이 아닌 걸까요?

(질문자: NSUser)

(역주: 정렬을 하면 원래 있던 위치 값이 없어질테고... 정렬 자체의 비용도 굉장하겠군요.)

A: 선형 검색 (역주: 처음부터 그냥 하나씩 비교해서 값을 찾는 것)을 하세요. 아마 대부분 경우 값이 1 이상 차이날 겁니다. 이 경우, 예를 들면 array[i] == 4 일 때 찾는 값이 7이라면, 우리가 찾는 값은 적어도 앞으로 3번째 이후에 나오게 될테니 다음 인덱스를 i+3으로 설정하세요. while 루프를 이용해서 직접 다음 번 가능성있는 후보로 이동시키세요.

이 내용을 구현하면 아래와 같습니다. 약간 일반화 된 버전입니다. 찾는 값이 k 이고, 리턴 값이 -1이면 찾는 값이 없다는 뜻입니다.

#include <stdio.h>
#include <stdlib.h>

int first_occurence(int k, int array[], int n);

int main(void){
    int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8};
    printf("7 first occurs at index %d\n",first_occurence(7,a,15));
    printf("but 9 first \"occurs\" at index %d\n",first_occurence(9,a,15));
    return 0;
}

int first_occurence(int k, int array[], int n){
    int i = 0;
    while(i < n){
        if(array[i] == k) return i;
        i += abs(k-array[i]);
    }
    return -1;
}

출력:

7 first occurs at index 11
but 9 first "occurs" at index -1

(답변자: John Coleman)

_

Efficient way to search an element

up vote64down votefavorite 17

Recently I had an interview, where they asked me a "searching" question. The question was: Assume there is an array of (positive) integers, of which each element is either +1 or -1compared to its adjacent elements. Example: array = [4,5,6,5,4,3,2,3,4,5,6,7,8]; Now search for 7 and return its position. I gave this answer: Store the values in a temporary array, sort them, and then apply binary search. If the element is found, return its position in the temporary array. (If the number is occurring twice then return its first occurrence) But, they didn't seem to be satisfied with this answer. What is the right answer? c algorithm sorting search shareeditflag edited Dec 28 '15 at 13:31 Simon Klaver 19315 asked Dec 27 '15 at 14:56 NSUser 378110

_

101down voteaccepted

You can do a linear search with steps that are often greater than 1. The crucial observation is that if e.g. array[i] == 4 and 7 hasn't yet appeared then the next candidate for 7 is at index i+3. Use a while loop which repeatedly goes directly to the next viable candidate. Here is an implementation, slightly generalized. It finds the first occurrence of k in the array (subject to the +=1 restriction) or -1 if it doesn't occur: #include <stdio.h> #include <stdlib.h> int first_occurence(int k, int array[], int n); int main(void){ int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8}; printf("7 first occurs at index %d\n",first_occurence(7,a,15)); printf("but 9 first \"occurs\" at index %d\n",first_occurence(9,a,15)); return 0; } int first_occurence(int k, int array[], int n){ int i = 0; while(i < n){ if(array[i] == k) return i; i += abs(k-array[i]); } return -1; } output: 7 first occurs at index 11 but 9 first "occurs" at index -1 shareeditflag edited Dec 30 '15 at 1:31 answered Dec 27 '15 at 15:02 John Coleman 10.1k41133