Why does mi interpolation search not return the corresponding index when the searched key is the last vector value?

Issue

This Content is from Stack Overflow. Question asked by Aaron_Serpilin

I am trying to create an interpolation search algorithm using both a linear search and a binary search that only splits in half the list once. For both circumstances, the algorithm works except when the desired value is the last item in the vector, in which case the valIndex variable returns an unexpected result. For all other cases, the correct index is returned. Below I will leave the code of the linear search and the binary search. What is wrong with my linear and binary loop that does not allow the index of the last item to be returned?

Linear Search

#include <iostream>
#include <vector>

using namespace std;

int main () {

    int listVal;
    int searchedVal;
    int valIndex;
    vector<int> orderedList;

    cout << "Enter the ordered list: " << endl;

    while (cin >> listVal && cin.peek() != 'n') {
        orderedList.push_back(listVal);
    };

    cout << "Enter the desired key: " << endl;
    cin >> searchedVal;

    //Linear Search
    for (int i = 0; i < orderedList.size(); i++) {

        int currVal = orderedList.at(i);
        
        if (currVal == searchedVal) {
            valIndex = i;
        }

    };

    cout << "The index of the key is: " << valIndex << endl;

};

Binary search

#include <iostream>
#include <vector>

using namespace std;

int main () {

    int listVal;
    int searchedVal;
    int valIndex;
    vector<int> orderedList;

    cout << "Enter the ordered list: " << endl;

    while (cin >> listVal && cin.peek() != 'n') {
        orderedList.push_back(listVal);
    };

    cout << "Enter the desired key: " << endl;
    cin >> searchedVal;

    //Binary Search
    if (searchedVal == orderedList.at(orderedList.size() / 2)) {
        valIndex = orderedList.size() / 2;
    } else if (searchedVal < orderedList.at(orderedList.size() / 2)) {
        for (int i = 0; i < orderedList.size() / 2; i++) {
            if (orderedList.at(i) == searchedVal) {
                valIndex = i;
            };
        };
    } else if (searchedVal > orderedList.at(orderedList.size() / 2)) {
        for (int j = orderedList.size() / 2; j < orderedList.size(); j++) {
            if (orderedList.at(j) == searchedVal) {
                valIndex = j;
            };
        };
    };

    cout << "The index of the key is: " << valIndex << endl;

};



Solution

This question is not yet answered, be the first one who answer using the comment. Later the confirmed answer will be published as the solution.

This Question and Answer are collected from stackoverflow and tested by JTuto community, is licensed under the terms of CC BY-SA 2.5. - CC BY-SA 3.0. - CC BY-SA 4.0.

people found this article helpful. What about you?