Cannot access vector[0] index

[StMick]

Hello!

Any advice on the code below would be appreciated.

I keep getting a segmentation fault stating "cannot access memory at address ..." where it is referring the call to v[0] in the first if statement.

Assuming vector v is already filled with data, what could be the reason for this?

  bool found(vector<int> v, int trgt, int left, int right){
    
    if(trgt < v[0] || trgt > v[v.size()-1]){
        return false;
    } else {
        int i = right - left;
        i /= 2;
        if(i == 0 && v[i] != trgt){
            return false;
        }
        if(v[i] == trgt){
            return true;
        } else {
            if(v[i] > trgt){
                return found(v,trgt,left, i);
            } else {
                return found(v,trgt,i, right);
            }
        }
    }
}

[deleted account xyzzy]

The C++ stdlib already contains algorithms to find data within C++ containers, including std::vector.

https://legacy.cplusplus.com/reference/algorithm/find/
https://en.cppreference.com/w/cpp/algorithm/find

The results of the search is an iterator for the vector. Iterators are something you should become familiar with when mucking around so you don't have to deal with the old school operator[].

[lastchance]

Assuming vector v is already filled with data

Don't assume anything. Check!
(e.g., print out v.size())

It wouldn't be a bad idea to check that v[] is sorted as well. (Your algorithm won't work if it isn't.)


Believe me, v[v.size()-1] will be even worse than v[0] if v does happen to be empty.

[AbstractionAnon]

Line 1: You're passing vector<int> v by value. This means that every time you call found (including the recursive calls), the run time has to make a copy of your vector on the stack. I don't know how big your vector is, but passing a vector by value is a bad idea. You should be passing it as an const ref.

bool found(const vector<int>& v, int trgt, int left, int right)

[lastchance]

BTW, you will be looking at v[0] whilst searching a range from i to right!

i would be better set as
left + ( right - left ) / 2
and you should look at v[left] rather than v[0].

[seeplus]

Consider (when v is sorted ascending):

#include <vector>
#include <iostream>
#include <iomanip>

bool found1(const std::vector<int>& v, int trgt, size_t left, size_t right) {
	if (left > right)
		return false;

	const auto i { left + (right - left) / 2 };

	if (v[i] == trgt)
		return true;

	if (v[i] > trgt)
		return found1(v, trgt, left, i - 1);

	return found1(v, trgt, i + 1, right);
}

bool found(const std::vector<int>& v, int trgt) {
	if (v.empty() || trgt < v.front() || trgt > v.back())
		return false;

	return found1(v, trgt, 0, v.size() - 1);
}

int main() {
	const std::vector list { 3, 6, 8, 10, 12, 23, 78 };

	std::cout << "3  " << std::boolalpha << found(list, 3) << '\n';
	std::cout << "10 " << std::boolalpha << found(list, 10) << '\n';
	std::cout << "78 " << std::boolalpha << found(list, 78) << '\n';
	std::cout << "66 " << std::boolalpha << found(list, 66) << '\n';
	std::cout << "1  " << std::boolalpha << found(list, 1) << '\n';
	std::cout << "99 " << std::boolalpha << found(list, 99) << '\n';
}

which displays:

3  true
10 true
78 true
66 false
1  false
99 false