Cannot access vector[0] index

Jan 13, 2023 at 1:38pm
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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  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);
            }
        }
    }
}
Jan 13, 2023 at 2:12pm
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[].
Jan 13, 2023 at 3:18pm
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.
Last edited on Jan 13, 2023 at 3:21pm
Jan 13, 2023 at 4:09pm
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)


Last edited on Jan 13, 2023 at 4:10pm
Jan 13, 2023 at 4:16pm
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].
Jan 13, 2023 at 5:21pm
Consider (when v is sorted ascending):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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

Last edited on Jan 13, 2023 at 5:24pm
Topic archived. No new replies allowed.