C++ Programming (Binary Search) Using part of the code from question 1 provided

Question

C++ Programming (Binary Search)

Using part of the code from question 1 provided below , you can start from step 3 in this question.

Here is the relevant portions of previous code to get the sorted array.

#include <iostream>
#include <fstream>

using namespace std;

void printArray(int arr[], int n);
void selectsort_ascending(int arr[], int n);

int main()

{
  
        // declaring an array
       int randomnums[20];
        int size = 0;
       int num;
  
       // opening and reading from file
       ifstream inputFile;
       inputFile.open("numbers.txt");

       while(size < 20 && inputFile >> num)
       {
        randomnums[size] = num;
       size++;
       }
  
       // printing
       printArray(randomnums, size);
      
       inputFile.close();
  
       //calling selection sort
       selectsort_ascending(randomnums, size);
  
       // printing
       printArray(randomnums, size);

return 0;

}

void printArray(int arr[], int n)
{
  
       for(int i=0; i<n; i++)
        cout << arr[i ]<< " ";
      
       cout << endl;
}

void selectsort_ascending(int arr[], int n)
{
       //pos_min is short for position of min
        int pos_min,
           temp;

       for (int i = 0; i < n - 1; i++)
       {
            pos_min = i;//set pos_min to the current index of array
  
        for (int j = i + 1; j < n; j++)
       {
             if (arr[j] < arr[pos_min])
                 pos_min=j;
        //pos_min will keep track of the index that min is in, this is needed when a swap happens
       }
  
        //if pos_min no longer equals i than a smaller value must have been found, so a swap must occur
          if (pos_min != i)
           {
               temp = arr[i];
               arr[i] = arr[pos_min];
               arr[pos_min] = temp;
           }
       }
}

Explanation / Answer

Program:

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
void printArray(int arr[], int n);
void selectsort_ascending(int arr[], int n);
int bsf(int arr[], int start,int last, int searchNum, int size);
int main()
{
  
// declaring an array
int randomnums[20];
int size = 0;
int num,uin,searchNum;
  
// opening and reading from file
ifstream inputFile;
inputFile.open("numbers.txt");

while(size < 20 && inputFile >> num)
{
randomnums[size] = num;
size++;
}
cout<<"Unsorted array : "<<endl;
// printing
printArray(randomnums, size);
  
inputFile.close();
  
//calling selection sort
selectsort_ascending(randomnums, size);
  
cout<<"Sorted array : "<<endl;
// printing
printArray(randomnums, size);

cout<<"Enter UIN :"<<endl;

cin>>uin;

searchNum=uin%50;

   cout<<"Number to search : "<<searchNum<<endl;

cout<<"Closest Index is : "<<bsf(randomnums,0,size-1,searchNum,size);

return 0;
}
void printArray(int arr[], int n)
{
  
for(int i=0; i<n; i++)
cout << arr[i ]<< " ";
  
cout << endl;
}
void selectsort_ascending(int arr[], int n)
{
//pos_min is short for position of min
int pos_min,
temp;
for (int i = 0; i < n - 1; i++)
{
pos_min = i;//set pos_min to the current index of array
  
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[pos_min])
pos_min=j;
//pos_min will keep track of the index that min is in, this is needed when a swap happens
}
  
//if pos_min no longer equals i than a smaller value must have been found, so a swap must occur
if (pos_min != i)
{
temp = arr[i];
arr[i] = arr[pos_min];
arr[pos_min] = temp;
}
}
}
int bsf(int arr[], int start,int last, int searchNum, int size)
{
int mid;
if(start > last)
{
  
   int before=last-1,after=last+1,diff1,diff2,diff3,curr;
   if(last < 0)
       curr=start;
   else
       curr=last;
   diff1=abs(arr[curr]-searchNum);
   if(diff1==0)
       return curr;
   if(before>0)
   {
       diff2=abs(arr[before]-searchNum);
   }
   else
   {
       diff2=diff1+1;
   }
   if(after<size)
   {
       diff3=abs(arr[after]-searchNum);
   }
   else
   {
       diff3=diff1+1;
   }
   if(diff2<diff3 && diff2<diff1)
       return before;
   else if(diff3<diff2 &&diff3<diff1)
       return after;
   else return curr;
}
else
   {
       mid=(last+start)/2;
  
   if(arr[mid]==searchNum)
       return mid;
   else if(arr[mid]<=searchNum)
       bsf(arr,mid+1,last,searchNum,size);
   else
       bsf(arr,start,mid-1,searchNum,size);
   }
  
}

Numbers.txt:

1 5 6 9 0

Output:

Unsorted array :
1 5 6 9 0
Sorted array :
0 1 5 6 9
Enter UIN :
579
Number to search : 29
Closest Index is : 4

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.