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;
           }
       }
}

  

2. Binary Search (20 Points) Use the sorted array that you get after Step 3 from question 1 (you can re-use the relevant portions of previous code to get the sorted array). The input file name is numbers.txt. The testing input file will contain 20 random integers in the interval [o, 50]. 1. 2. 3. Use C-style array rather than STL vector. No global variables are allowed. Print the elements of the sorted array in main. (same as step 4 from previous question) Use your own binary search function called bsf to find a number (passed as one of the parameters), which is your UIN modulus 50. You have to hard code this inside your main function. For example: If your UIN is****123 Search for number 23 a. Print the number (e.g. 23) b. Report the index of the number in sorted array which is closest to the number being searched 4. Ask user to input another integer. Perform binary search and report the index of the number which is closest to the number being searched. For example, the sorted array sorted_array is 1,2,2,4,.,40,48,50 and the input number to be searched is -100. Your program should output 0 because sorted_array[0] is the one closet to -100 among all 20 integers. Note: Ensure that the output displayed on the terminal screen is interpretable.

Explanation / Answer

I wrote bsf function, that returns index if number found in sorted array, else it returns index of closest element(ceil of number)

#include <iostream>
#include <fstream>
using namespace std;
void printArray(int arr[], int n);
void selectsort_ascending(int arr[], int n);
int bsf(int arr[], int low,int high, int key);
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);
  
int key;
cout<<" Enter number to be search: ";
cin>>key;
  
int index = bsf(randomnums, 0, 19, key%50);
               cout<<key<<" found at index "<<index<<endl;
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 low, int high, int x)
{
   int mid;

/* If x is smaller than or equal to the first element,
then return the first element */
if(x <= arr[low])
return low;

/* If x is greater than the last element, then return -1 */
if(x > arr[high])
return -1;

/* get the index of middle element of arr[low..high]*/
mid = (low + high)/2; /* low + (high - low)/2 */

/* If x is same as middle element, then return mid */
if(arr[mid] == x)
return mid;

/* If x is greater than arr[mid], then either arr[mid + 1]
is ceiling of x or ceiling lies in arr[mid+1...high] */
else if(arr[mid] < x)
{
if(mid + 1 <= high && x <= arr[mid+1])
return mid + 1;
else
return bsf(arr, mid+1, high, x);
}

/* If x is smaller than arr[mid], then either arr[mid]
is ceiling of x or ceiling lies in arr[mid-1...high] */   
else
{
if(mid - 1 >= low && x > arr[mid-1])
return mid;
else
return bsf(arr, low, mid - 1, x);
}
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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