이진 검색 : 최소값이

Question

보다 작음

다음 C 프로그램은 search보다 작은 값으로 배열을 검색합니다. "array"의 값이 양의 정수인 경우이 값을 임의의 배열 길이로 추정 할 수 있습니까? 사전에

#include <stdio.h> 

int main() 
{ 
    int array[11] = { 1, 5, 9, 15, 37, 49, 56, 65, 74, 90, 95}; 

    int first = 0; 
    int last = 10; 
    int search = 95; 
    int middle = (first+last)/2; 

    while (first <= last) { 
     if (array[middle] < search) 
      first = middle + 1;  
     else if (array[middle] > search) 
      last = middle - 1; 
     else break; 

     printf("first= %d,last= %d, middle= %d, search= %d\n", first, last, middle, search); 
     middle = (first + last)/2; 
    } 

    printf("middle = %d\n", array[middle]); 
} 

Thaks, 호세 루이스

당신은 while 루프에서 1 개 라인을 누락

Answer 1

.

#include <stdio.h> 

int main() 
{ 
    int array[11] = { 1, 5, 9, 15, 37, 49, 56, 65, 74, 90, 95}; 

    int first = 0; 
    int last = 11; 
    int search = 95; 
    int middle = (first+last)/2; 

    while (first <= last) { 
     middle = (first + last)/2; //this line 
     if (array[middle] < search) 
      first = middle + 1; 
     else if (array[middle] > search) 
      last = middle - 1; 
     else 
     { 
      printf("Found"); 
      return 0; 
     } 
    } 
    printf("Not found"); 
    return 0; 
} 

첫 번째 요소 또는 마지막 요소를 변경할 때 중간을 초기화해야합니다. 이것은 작은 프로그램이기 때문에 매번 그것을했습니다. 그래서 공연에 큰 피해를주지는 않을 것입니다. 이렇게하지 않으면 중간 요소가 검색 할 때 첫 번째 요소 앞에 머물러 있으며 원하는 요소가 아닌 것입니다.

Answer 2

예, array_size에 필요한 크기를 설정하여 배열을 가질 수 있지만 배열에 주문 번호를 입력해야합니다. last 변수를 array_size - 1보다 낮은 값으로 변경할 수도 있습니다. 이 경우 8하지만 검색 결과는 8까지 제한됩니다.

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

int main(void) 
{ 
    int i; 
    int array_size = 11; 
    int *array = malloc(sizeof(int) * array_size); 

    for (i = 0; i < array_size; i++) 
     scanf("%d", &array[i]); 

    for (i = 0; i < array_size; i++) 
     printf("%d \t", array[i]); 
     printf("\n"); 

    int first = 0; 
    int last = array_size - 1; 
    int search = 7; 
    int middle = (first+last)/2; 

    while (first <= last) 
    { 
     if (array[middle] < search) 
      first = middle + 1; 

     else if (array[middle] > search) 
      last = middle - 1; 

     else 
     { 
      printf("%d found at indext %d\n", array[middle], middle); 
      return 0; 
     } 

     middle = (first + last)/2; 
     printf("first= %d,last= %d, middle= %d, search= %d\n", 
       first, last, middle, search); 
    } 

    printf("%d: Element not found\n", search); 
    return -1; 
}