C++

Forum

 
Binary Search

d1g1talarts (55)
I am attempting to implement this binary search but it returns 11 and says 12 cannot be found. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
int binSearch(const vector<int>& sorted, const int target) {
	const int mid = floor(sorted.size() / 2);

	if (sorted[mid] == target) {
		//return if it matches
		return mid;
	}
	else if (sorted[mid] > target) {
		//search left
		const vector<int> left(sorted.begin(), sorted.begin() + mid);
		return binSearch(left, target);
	}
	else {
		//search right
		const vector<int> right(sorted.begin() + mid, sorted.end());
		return (mid + binSearch(right, target));
	}
}


1
2
3
4
5
6
7
8
9
10
11
 
//test
vector<int> checkVal = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
	vector<int> inputTest = { 15,12,13,11,9,10,7,8,14,6,5,3,4,2,1 };
int tempVal = binSearch(inputTest, 12);
	if (tempVal == 12) {
		found == true;
		cout << "binSearch can find 12: " << tempVal<<"\n";
	}
	else {
		cout << "binSearch can't find 12 : " << tempVal<<"\n";
}

tpb (1495)
You need to use checkVal (the sorted array), not inputTest in the call to binSearch.
d1g1talarts (55)
i sort the vector, but i tried that out anyways and sadly i get the same result.
Returns 11 and says 12 isnt in the array
tpb (1495)
You can make it work something like this.
Usually you wouldn't want to be making copy after copy of the vector halves when there's no reason to. So usually we would pass indices (or pointers or iterators) and never copy the vector. The second version does that. You can enable it by changing "#if 1" to "#if 0"
I also made it take in the search value from the command line.
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

#if 1

int binSearch(const vector<int>& sorted, int target) {
    int mid = sorted.size() / 2;

    if (sorted.size() == 0)
        return -1;
    if (sorted[mid] == target)
        return mid;
    if (sorted.size() == 1)
        return -1;

    if (sorted[mid] > target)
        return binSearch(vector<int>(sorted.begin(), sorted.begin() + mid), target);
    else {
        int x = binSearch(vector<int>(sorted.begin() + mid + 1, sorted.end()), target);
        return x == -1 ? -1 : mid + x;
    }
}

#else

int binSearch2(const vector<int>& sorted, int lo, int hi, int target) {
    if (lo >= hi)
        return -1;
    int mid = lo + (hi - lo) / 2;
    if (target == sorted[mid])
        return mid;
    else if (target < sorted[mid])
        return binSearch2(sorted, lo, mid, target);
    else
        return binSearch2(sorted, mid + 1, hi, target);
}

int binSearch(const vector<int>& sorted, int target) {
    binSearch2(sorted, 0, sorted.size(), target);
}
#endif

int main(int argc, char **argv) {
    int key = 9;
    if (argc == 2)
        key = atoi(argv[1]);
    vector<int> checkVal = { 1,2,3,4,5,6,7,8,10,11,12,13,14,15,16 };
    int index = binSearch(checkVal, key);
    if (index == -1)
        cout << "binSearch can't find " << key << "\n";
    else
        cout << "binSearch found " << key << " at position " << index << "\n";
}

Last edited on
d1g1talarts (55)
I am an idiot. i need to be checking the location. not the value. Thanks guys!
Topic archived. No new replies allowed.