C에서 정렬 된 배열 검색

Question

C에서 문제를 해결하기 위해 노력하고 있습니다. 그것에 대해 빠른 질문이 있습니다. 문제는 다음과 같습니다. 정수 정렬 된 배열을 받았습니다 (예 : a[i] = { 1, 2, 3, 3, 3 }). 자, 주어진 정수를 검색하고, 배열에서 첫 번째 발생 위치와 그 정수의 발생 횟수를 반환하는 프로그램을 실행해야합니다.

따라서 3을 검색하면 a[2]에 첫 번째 어커런스가 표시되고 3은 세 번 있습니다. 첫 번째 부분은 첫 번째 항목을 찾으려면 문자열 헤더 파일의 strcspn을 사용하면됩니다. 그러나 두 번째 부분에는 인스턴스 수를 세는 inbuilt 함수가 있습니까?

실제로 카운터 변수를 증가시킴으로써 "맨손"으로이 작업을 수행 할 수 있습니다. 그러나 교수님은 리턴 타입이 size_t 여야한다는 힌트를 주셨고, 일부 내장 함수를 사용할 수 있다고 제안했습니다. 어떤 도움을 주시면 감사하겠습니다.

감사합니다, 알렉산더

Answer 1

아니,이 작업을 수행하는 표준 기능이 없다. 교수님은 리턴 타입이 size_t이어야한다고 말했습니다. 왜냐하면 그것은 메모리에있는 객체의 크기 나 개수를 계산할 때 사용할 표준 타입이기 때문입니다. 일부 시스템에서는 "unsigned int"유형이 충분히 클 수 없습니다.

Answer 2

힌트 : 지정된 배열이 이미 주어진 정수의 인스턴스를 찾기 위해 이진 검색을 사용하여 당신이를 선두를 찾을 때까지 뒤로 걸을 수 분류되어 있기 때문에, 다음 더 이상 일치 할 때까지 위치를 증가.

Answer 3

strcspn이 도움이 될 것이라고 생각하지 않습니다. 문자열 (문자 배열)에서 작동하지만 int 배열이 있다고합니다. 다른 사람들은 이미 내가 무엇을 말할 것인지 말했습니다.

Answer 4

카운터로 size_t 변수를 사용할 수 있습니다. 그러나 더 나은 접근법은 바이너리 검색 (라이브러리 함수가 있음)을 사용하여 인스턴스 중 하나를 찾고 거기에서 앞뒤로 검색하는 것입니다.

Answer 5

x를 검색하면 이진 탐색을 사용하여 x의 첫 번째 발생을 찾아 x (또는 배열의 끝)보다 큰 정수의 첫 번째 발생을 다른 조건을 사용하여 왼손 및 오른손을 설정하여 찾을 수 있습니다 검색 창의 측면.

의사 코드에서 간단한 이진 검색 :

left,right = 0, n 

while right - left > 1 
    mid = left + right/2 
    if array[mid] < x 
    left = mid 
    else 
    right = mid 

는 당신이 여기 변경해야하는 것은입니다 그건 당신이있는 경우에 검색 창 왼쪽 또는 오른쪽을 가지고 여부를 결정합니다. 두 개의 검색, 하나는 x-es 시퀀스의 왼쪽을 찾으며, 다른 하나는 오른쪽을 찾는다.이 두 가지의 차이점은 엔트리의 수이다.