0

so i wrote a program that is suppose to have a array that has random numbers in it. sort the array, and then do a binary search and interpolation search to find the number and how many comparisons it took. i get it to work sometimes but the comparisons are not working and sometimes when i know the array has the number it says it is wrong. help please

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int sort(int arr[],int);
int binarysearch(int arr[],int key,int size);
int interpolationsearch(int arr[],int size,int key);

int cmp=0;
int cmps=0;

int main()
{       int num, results,find, size;
        cout<<"how big do u want the array size? ";
        cin>>size;

        int arr[size];
        srand((unsigned)time(0));

        for(int i=0;i<size;i++)
        {       arr[i] = (rand()%100)+1;
        cout << arr[i] << endl;
        }

        sort(arr,size);

        cout<<"enter a number to look up: ";
        cin>> num;

        results= binarysearch(arr,size,num);

        find=interpolationsearch(arr,size,num);

        if(results == -1)
        {       cout<<"the number is not in the binary array"<<endl;
        }else
        {       cout<<"the number for binary search is: "<< num <<
                "with comparisions of: "<<cmp<<endl;
        }

        if(find==-1)
        {       cout<<"the number is not in interpolation array"<<endl;
        }else
        {       cout<<"the number in interpolation search is: "<< num <<
                "with comparisons of: "<<cmps<<endl;
        }

return 0;
}
int binarysearch(int arr[],int key, int size)
{
        int top=0;
        int bot=size-1;
        int mid=(top + bot)/2;

      while(top <= bot){
        cmp++;
        if(key==arr[mid]){
          return mid;
        }else if(key<arr[mid]){
          bot=mid-1;
        }else{
          top=mid+1;
        }
          return -1;
      }
}


int interpolationsearch(int arr[], int size, int key){
         int low = 0, high = size - 1, mid;

         while (arr[low] < key && arr[high] >= key)
        { mid = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]);
        cmps++;
        if (arr[mid] < key)
        {       low = mid + 1;
        }else if (arr[mid] > key)
        {       high = mid - 1;
        }else
        { return mid;
        }
        }//end while

        cmps++;
        if (arr[low] == key)
        {
                return low;
        }else
        {
        return -1;
        }
}//end interpolation Search Function


int sort(int arr[], int vals)
 {      int temp;

                for(int cnt=0; cnt< (vals-1);cnt++)
                {
                        if(arr[cnt]>arr[cnt+1])
                        {       temp=arr[cnt];
                                arr[cnt]=arr[cnt+1];
                                arr[cnt+1]=temp;
                        }
                }
}
2
Contributors
1
Reply
2
Views
8 Years
Discussion Span
Last Post by firstPerson
0

This is not right :

int sort(int arr[], int vals)
 {
      int temp;
 
            for(int cnt=0; cnt< (vals-1);cnt++)
              {
                       if(arr[cnt]>arr[cnt+1])
                        {       temp=arr[cnt];
                                arr[cnt]=arr[cnt+1];
                                arr[cnt+1]=temp;
                        }
                }
}
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.