양면 검색을 사용하여 배열에서 문자열 제거

Question

두 가지 기능이 있습니다. Find 함수는 키를 찾고 그 위치를 반환 할 때까지 섹션별로 배열을 검색하는 이중 단면 검색을 수행합니다. 함수 removef 또는 (빠른 제거)는 해당 위치를 잡고 문자열 배열에서 제거합니다. 사용자에게 명령 및 문자열 (제거되는 문자열)을 입력하도록 요청하는 명령 줄 인터페이스를 사용하므로 사용자에게 문자열을 묻는 것은 불필요합니다. 여기

은 찾기 기능 키 (중간 중간 위 또는 아래에) 어레이의 상부 또는 하부에 있는지 여부를 결정하도록되어

int StringList::Find(string key, int start, int end) 
{ 
    int middle = (end + start)/2; 
    if (key > str[middle]) 
    { 
     return Find(key,middle,end); 
    } 
    else if (key < str[middle]) 
    { 
     return Find(key,start,middle); 
    } 
    else if (key == str[middle]) 
    { 
     return middle; 
    } 
} 

내 찾기 기능 다음이 발견 될 때까지, 분할 계속 인 삭제해야 할 키 또는 문자열 여기

는 removef입니다 :

void StringList::removef(string s) 
{ 
    int loc = Find(s,0,10000); //ignore these parameters, i know they are wrong they are just an example 


     for(int j=loc; j<(numberOfStrings)-1; j++) 
     { 
      str[j] = str[j+1]; 
     } 
     numberOfStrings--; 

} 

내 문제는 내 찾기 기능은 이중 단면 검색을 사용하여입니다. 내가 고칠 수있는 어떤 제안이라도? 나는 정말로 붙어 있었다. 감사!

Answer 1

내가 볼 수있는 한 가지 문제점은 키가 중간 요소보다 크면 [midde,end]으로 새 범위를 설정하지만 [middle+1,end]이어야한다는 것입니다. 중간 요소를 다시 고려할 필요가 없습니다. 그것이 일치하지 않는 것을 아십시오.

그래서 첫 번째 조건은 다음과 같아야합니다

if (key > str[middle]) 
{ 
    return Find(key,middle+1,end); 
} 

을 또한, 다른 언급, 당신은 문자열 배열에없는 있는지 확인하기 위해 검사가 필요합니다. 귀하의 Find 메소드의 시작 부분에 이와 같은 것을 추가 할 것을 제안합니다. 당신이 시작이 검색 더 이상 공간이 없습니다 당신의 문자열을 찾을 수 wron't, 끝을 동일 지점까지 배열을 세분화하면

if (start == end) return -1; 

.

그 외, 내가 잘못 생각할 수있는 유일한 점은 잘못된 범위로 Find 메서드를 호출하고 있다는 것입니다. 다음과 같이 호출해야합니다.

int loc = Find(s,0,numberOfStrings); 

Answer 2

시작하려면 문자열 'str'배열을 이미 정렬했다고 가정합니다 ... 그렇지 않으면 이진 검색이 작동하지 않습니다.

'찾기'함수에서 문자열 배열로 가정하는 'str'배열에 액세스하지만이 배열을 매개 변수로 전달하지 않습니다. 따라서 액세스하려고 시도하는 전역 배열이 아니면 않는 한 작동하지 않습니다.

마지막으로,이 함수를 재귀 적으로 호출하기 때문에 배열에 전혀 포함되지 않은 문자열을 처리해야합니다.