Add an additional method to do binary search and find whether user-specified val

Question

Add an additional method to do binary search and find whether user-specified value exists. You can return the index if it is found, -1 otherwise. main() can print approriate message based on the return value. Here is the sample inputs/outputs:

Sample run #1:

Enter value: 45

45 was found at index 5

Sample run #2:

Enter value: 44

44 was not found in the array.

Source Code:

#include<iostream>

#include<cstdlib>

using namespace std;

int items[] = {10, 5, 99, 45, 23, 37, 56, 84, 69, 11};

int n = 10;

void printArray() {

for(int i=0 ; i<n ; i++)

cout << items[i] << " ";

cout << endl;

}

void bubbleSort() {

for(int last=n-1 ; last>0; last--) {

// go from 0 to last

for(int i=0 ; i<last ; i++)

// is current item bigger than next item?

if (items[i] > items[i+1])

swap(items[i], items[i+1]);

printArray(); // just to print intermediate array contents

}

}

void selectionSort() {

int small, smallIndex;

for(int start=0 ; start<n ; start++) {

//find smallest item items[start ... n-1]

small = items[start];

smallIndex = start;

for(int i=start+1 ; i<n ; i++) {

if (small > items[i]) {

small = items[i];

smallIndex = i;

}

}

//swap items at start position & smallIndex position

swap(items[start], items[smallIndex]);

//print the intermediate array..

printArray();

}

int main() {

printArray();

selectionSort();

printArray();

}

Explanation / Answer

#include<iostream>
#include<cstdlib>

using namespace std;

int items[] = {10, 5, 99, 45, 23, 37, 56, 84, 69, 11};
int n = 10;

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

void bubbleSort() {
    for(int last=n-1 ; last>0; last--) {
        // go from 0 to last
        for(int i=0 ; i<last ; i++)
        // is current item bigger than next item?
            if (items[i] > items[i+1])
                swap(items[i], items[i+1]);
    }
}

void selectionSort() {
    int small, smallIndex;
    for(int start=0 ; start<n ; start++) {
        //find smallest item items[start ... n-1]
        small = items[start];
        smallIndex = start;
        for(int i=start+1 ; i<n ; i++) {
            if (small > items[i]) {
                small = items[i];
                smallIndex = i;
            }
        }
        //swap items at start position & smallIndex position
        swap(items[start], items[smallIndex]);
    }
}

int bsearch(int n) {
    int low = 0;
    int high = 9;
   
    while (low <= high) {
        int mid = (low + high) / 2;
        if (items[mid] == n)
            return mid;
        if (items[mid] < n)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

int main() {
    int n, index;
   
    selectionSort();
    cout << "Enter value: ";
    cin >> n;
   
    index = bsearch(n);
    if (index != -1)
        cout << n << " was found at index " << index << " ";
    else
        cout << n << " was not found in the array. ";
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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