이진 검색이 내가 이진 검색을 위해 작성한 코드입니다 키

Question

#include<stdio.h> 
#include<stdlib.h> 
int input(int *a) 
{ 
    int n,i; 
    printf("enter the no of elements:"); 
    scanf("%d",&n); 
    for(i=0;i<n;i++) 
    { 
     printf("enter the element:"); 
     scanf("%d",a++); 
    } 
    return n; 
} 
int key_input(int *a,int key) 
{ 
    int k; 
    printf("enter the key value which have to be searched in the array of no's provided:"); 
    scanf("%d",&k); 
    return k; 
} 
void binary_search(int *a,int n,int key) 
{ 
    int low=0; 
    int high=n-1; 
    int mid; 
    while(low<=high) 
    { 
     mid=(high+low)/2; 
     if(key == a[mid]) 
     { 
      printf("the key:%d is found at location:%d in the array",key,mid); 
      if(key==a[mid+1]) 
      { 
       binary_search(a+mid+1,n-mid-1,key); 
      } 
      if(key==a[mid-1]) 
      { 
       binary_search(a,n-mid-1,key); 
      } 
      if(key != a[mid-1] || key != a[mid+1]) 
       break; 
     } 
     else if(key < a[mid]) 
      high=mid-1; 
     else if(key>a[mid]) 
      low=mid+1; 
    } 
} 
int main() 
{ 
    int arr[100]; 
    int n=input(arr); 
    int key=key_input(arr,n); 
    binary_search(arr,n,key); 
    return 0; 
} 

의 모든 배열 위치를 찾아 C는-있습니다. 키가있는 모든 배열 위치를 찾고 싶습니다. 예를 들어, 입력 4,4,4,4에 대해 키를 4로 지정합니다. 출력에는 배열 (0-3)의 모든 위치가 포함되어야하지만 코드에 무엇이 잘못되었는지는 알 수 없으며 무한히 실행됩니다. 누군가 나를 도와주세요.

Answer 1

높은 값과 낮은 값을 이동하는 코드가 중간 값이 항상 동일하여 무한 루프가 발생하는 지점에 도달했을 가능성이 있습니다. 이것은 배열 목록의 항목 수와 항목 수가 2로 나눌 수 있는지 여부에 따라 다릅니다.

일반적으로 이진 검색을 수행 할 때 범위가 충분히 작 으면 범위의 마지막 몇 항목에 대해 순차 검색을 수행합니다.

오름차순으로 정렬되고 중복 항목이있을 수있는 정수 배열을 검색하고 검색중인 정수와 일치하는 첫 번째 배열 요소를 찾는 것처럼 들리는 것 같습니다.

하나의 질문은 일치하는 항목의 수를 제공하기 위해 검색을 수행하는이 기능을 원할지 아니면 처음 항목을 반환하고 기능 호출자가 다른 항목을 확인하도록할지 여부입니다.

다음은이 작업을 수행 할 함수에 대한 인터페이스를 고려하는 함수 프로토 타입입니다.

// search the integer array iValueArray which is a sorted list of integers 
// and return the index 0 to iNoArrayElements - 1 of the first integer matching 
// the value specified in iSearchValue. if a match is not found then return -1 
int FindFirstMatch (int iSearchValue, int *iValueArray, int iNoArrayElements); 

이 기능은 다음과 같을 것이다.

int FindFirstMatch (int iSearchValue, int *iValueArray, int iNoArrayElements) { 
int iRetIndex = -1; 

if (iNoArrayElements > 0) { 
    int iLowIndex = 0; 
    int iHighIndex = iNoArrayElements - 1; 
    int iMidIndex = (iHighIndex - iLowIndex)/2 + iLowIndex; 

    while (iLowIndex <= iHighIndex) { 
     int iCompare = (iSearchValue - iValueArray[iMidIndex]); 

     if (iHighIndex - iLowIndex < 5) { 
      // range is small so just do a straight sequential search 
      for (iMidIndex = iLowIndex; iMidIndex <= iHighIndex; iMidIndex++) { 
       int iCompare = (iSearchValue - iValueArray[iMidIndex]); 
       if (iCompare == 0) { 
        // search value equals the mid so we have found a match 
        // now we need to move lower until we find the first of 
        // the series of matching items. 
        iRetIndex = iMidIndex; 
        break; 
       } 
      } 
      break; 
     } 
     if (iCompare < 0) { 
      // search value is lower than mid so move to range below mid 
      iHighIndex = iMidIndex; 
     } else if (iCompare > 0) { 
      // search value is higher than mid so move to range above mid 
      iLowIndex = iMidIndex; 
     } else { 
      // search value equals the mid so we have found a match 
      // now we need to move lower until we find the first of 
      // the series of matching items. 
      iRetIndex = iMidIndex; 
      break; 
     } 
     iMidIndex = (iHighIndex - iLowIndex)/2 + iLowIndex; 
    } 
} 

if (iRetIndex > 0) { 
    while (iRetIndex > 0 && iValueArray[iRetIndex - 1] == iSearchValue) { 
     iRetIndex--; 
    } 
} 
return iRetIndex; 

}