c - Interpolation Search Program?

Question

When I enter a value up to about 200000, there is no problem with it. But if I search a bigger value program just does nothing. Just passes one row down and wait. What is the problem with this?

#include<stdio.h>
#include<conio.h>
int isearch(int a[],int key);
int main()
{
  int arr[20000],n,i,key,mid;


  FILE *fptr;

  //read sorted list file!
  if((fptr = fopen("sorted.txt","r"))==NULL){
    printf("Error in reading file !\n");
    return 0;
  }
  //array of sorted list!
  while(!feof(fptr)){
    if(!feof(fptr)){
      fscanf(fptr,"%d",&arr[i]);
      i++;}

  }

  printf("\nEnter element to be found:");
  scanf("%d",&key);
  mid=isearch(arr,key);
  printf("\nFound at position %d",mid+1);
  getch();
  return 0;
}
int isearch(int a[],int key)
{
  int low=0,high=19999,mid;
  while(a[low]<key&&a[high]>=key)
  {
    mid=low+(high-low)*(key-a[low])/(a[high]-a[low]);
    if(a[mid]<key)
      low=mid+1;
    else if(a[mid]>key)
      high=mid-1;
    else
      return mid;
  }
  if(a[low]==key)
    return low;
  else
    return -1;
}

Answer 1

Your algorithm assumes that all of the values of a have been set, but you don't guarantee that ... what if your file has fewer than 20000 entries?

And suppose that arr[19999] is, say, 100000, and you search for 200000, mid will be set to a value greater than high and you get undefined behavior. You need to check that mid is within low .. high. And to avoid the first problem, you should pass low and high as parameters to your search function (or just the array size == high + 1, since low is always initially 0).

I suggest looking at any of the numerous examples of interpolation search algorithms available on-line and in books on algorithms.