Hi guys, so i was just playing around with c++, trying to get back on track after a long long time away into Generic GC langs. As a polyglot programmer, its my duty to stay up to date with all my languages.

So , here's the dig. I was playing with algorithms...binary search to be exact. so, i encountered some issues along the way. which actually gave me some serious debug time!
So i thought, why not share the fun....i'm throwing out this challenge to anyone who thinks he's as good a C++ programmer as he/she thinks, to fix this code snippet...don't write your implementation...we all can do that...just /fix?optimize/

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

/**
* Olyboy16; Implementation of a simpler binary search algo
* this algo is limited to O(log n * 2) instead of O(log n)
*/

template<typename T>
string binSearch(vector<int>* hay, const int pin){
	int size = hay->size();
	if(hay->at(size/2) > pin){
		vector<int>* hay2; // if you can eliminate this object...you're good!
		copy(hay->begin(), hay->end(), hay->begin());
		return binSearch<int>(hay2, pin);
	}
	//lets just search through the chop
	auto nd = find(hay->begin(), hay->end(), [=](int& x){
		return x == pin;
	});
	return "[val:"+nd+"]";
}

int main(){
	vector<int>* arr {2,5,6,7,9,5,2,1,89,76,33,56,12,0,98,5,4,3,2,45,654,99};
	sort(arr->begin(), arr->end(), [](int& i, int& j){ //current > later
		return i > j;
	});
	cout << "Finding 86 using binary search! = " << binSearch<int>(arr, 86);
}

Please note that i intentionally designed it to be a recursive solution...its just to pass time really.

Olyboy16:
Hi guys, so i was just playing around with c++, trying to get back on track after a long long time away into Generic GC langs. As a polyglot programmer, its my duty to stay up to date with all my languages.

So , here's the dig. I was playing with algorithms...binary search to be exact. so, i encountered some issues along the way. which actually gave me some serious debug time!
So i thought, why not share the fun....i'm throwing out this challenge to anyone who thinks he's as good a C++ programmer as he/she thinks, to fix this code snippet...don't write your implementation...we all can do that...just /fix?optimize/

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

/**
* Olyboy16; Implementation of a simpler binary search algo
* this algo is limited to O(log n * 2) instead of O(log n)
*/

template<typename T>
string binSearch(vector<int>* hay, const int pin){
	int size = hay->size();
	if(hay->at(size/2) > pin){
		vector<int>* hay2; // if you can eliminate this object...you're good!
		copy(hay->begin(), hay->end(), hay->begin());
		return binSearch<int>(hay2, pin);
	}
	//lets just search through the chop
	auto nd = find(hay->begin(), hay->end(), [=](int& x){
		return x == pin;
	});
	return "[val:"+nd+"]";
}

int main(){
	vector<int>* arr {2,5,6,7,9,5,2,1,89,76,33,56,12,0,98,5,4,3,2,45,654,99};
	sort(arr->begin(), arr->end(), [](int& i, int& j){ //current > later
		return i > j;
	});
	cout << "Finding 86 using binary search! = " << binSearch<int>(arr, 86);
}

Please note that i intentionally designed it to be a recursive solution...its just to pass time really.

... Unfortunately, I don't think Your code is not salvageable... By any streak of luck :-( ...

It would require a significant change hence rewrite

---

---

Comments reserved on the code below...

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
/**
* Olyboy16; Implementation of a simpler binary search algo
* this algo is limited to O(log n * 2) instead of O(log n)
*/

---

Template Argument Deduction will not work here because
none of the arguments depends on the template parameters.
Even without Template Argument Deduction, I don't see any use of type `T` in the function-body below

template<typename T>
string binSearch(vector<int>* hay, const int pin){
    ....

Umm, I don't see any #include <string> up there...
Seriously? This function returns a `std::string`

---

	int size = hay->size();
	if(hay->at(size/2) > pin){

Oh boy....

---

Whaaaat?? For what? uninitialized pointer??
Even if `hay` was valid, the code below would invoke Undefined Behavior
wanted to use std::copy_backward instead?

		vector<int>* hay2;
		copy(hay->begin(), hay->end(), hay->begin());

---

Below, doesn't make any sense...
We are supposedly recursing with the exact parameters this function was called with?

                ......
		return binSearch<int>(hay2, pin);
	}

---

Below, We are dealing with built in types here, they have
bool operator == (T x, T y) defined for them by the compiler!! BTW `std::find` takes a ValueComparable type as the third argument...
since you are using some sort of Unary Predicate, wanted to use `std::find_if` instead?

	auto nd = find(hay->begin(), hay->end(), [=](int& x){
		return x == pin;
	});

---

What?

	return "[val:"+nd+"]";
}

---

What kind of nonsense is the declaration of arr?
std:: containers should be used as value types...
A pointer to any std:: container is more like code smell...

.....
int main(){
	vector<int>* arr {2,5,6,7,9,5,2,1,89,76,33,56,12,0,98,5,4,3,2,45,654,99};
        .....

---

Really? Any need to invent your functor here?
std::sort uses std::less<T> by default, if you want in descending,
why not simply use std::greater<int>?

	sort(arr->begin(), arr->end(), [](int& i, int& j){
		return i > j;
	});

..

Olyboy16:
....

Is that not Dr. Andrei Alexandrescu on your profile? ...The template goon...
I picked up D lang cause of that guy....

WhiZTiM:

Hey, calm down big guy! I wrote that code after over 2 years away from c++.
Also, that's not the actual working code, it was intentionally left buggy and dirty. Obviously carelessly written too.

Now down to the comments.

Clang and Mingw both support implicit <string> headers in their <iostream> header; and. ..just ignore those issues. it wasn't even a working code anyway, just part of a c++ rehab process(playing around with containers and lambdas).

Now just FTR, here is the actual code i wrote.

#include <iostream>
#include <algorithm>

using namespace std;

/**
* Olyboy16; Implementation of a simpler binary search algo
* this algo is limited to O(log n * 2) instead of O(log n)
*/

//function returns the index
template<typename T>
int binSearch(T arr[], int start, int end, T pin){
	if(start > end)
		return -1;
	int mid = (end-start)/2;
	if(arr[mid] > pin && (mid*2) > 4)
		return binSearch(arr, mid -1, end, pin);
	if(arr[mid] < pin && (mid*2) > 4)
		return binSearch(arr, start, mid +1, pin);
		
	return distance(arr, find(arr, arr + (mid*2), pin));
}

int main(){
	int list[] = {3,5,2,65,86,12,65,86,45,7,2,42,97};
	
	sort(begin(list), end(list));
	
	cout << "Finding 42 using binary search! = " << binSearch(list, 0, 11, 42);
}

just for PoC really. the result's half baked

WhiZTiM:

Is that not Dr. Andrei Alexandrescu on your profile? ...The template goon...
I picked up D lang cause of that guy....

Yes sir, that's the man! He's one of the guys i really wish to work with. D is just mehn..
I wonder why folks aren't picking it up much...such a great language

Hey, calm down big guy! I wrote that code after over 2 years away from c++.
Also, that's not the actual working code, it was intentionally left buggy and dirty. Obviously carelessly written too.

I am calm... very calm... But look at the title of your post, "Fix This C++ Code If You Can (dare)!".

---

Now down to the comments.
Clang and Mingw both support implicit <string> headers in their <iostream> header; and. ..just ignore those issues. it wasn't even a working code anyway, just part of a c++ rehab process(playing around with containers and lambdas).

Even if it worked, it would have been an Implementation Defined Behavior, according to ISO C++ standards...
...lol on the rehab process... Goodluck with it...

Now just FTR, here is the actual code i wrote.

/**
* Olyboy16; Implementation of a simpler binary search algo
* this algo is limited to O(log n * 2) instead of O(log n)
*/

//function returns the index
template<typename T>
int binSearch(T arr[], int start, int end, T pin){
	if(start > end)
		return -1;
	int mid = (end-start)/2;
	if(arr[mid] > pin && (mid*2) > 4)
		return binSearch(arr, mid -1, end, pin);
	if(arr[mid] < pin && (mid*2) > 4)
		return binSearch(arr, start, mid +1, pin);
		
	return distance(arr, find(arr, arr + (mid*2), pin));
}

The code is very very buggy...
And the interface is ... comments reserved

---

int main(){
	int list[] = {3,5,2,65,86,12,65,86,45,7,2,42,97};
	sort(begin(list), end(list));	
	cout << "Finding 42 using binary search! = " << binSearch(list, 0, 11, 42);
}

Bug spotted...

---

just for PoC really. the result's half baked

...lol. I know, like I said, I am only responding based on the title of your post.
Maybe the title of your post betrays your original intent... I dunno...

Olyboy16:


Yes sir, that's the man! He's one of the guys i really wish to work with. D is just mehn..
I wonder why folks aren't picking it up much...such a great language

Yea... you should check the work he has been pushing out... "Design by Introspection".

BTW, I like the design of your blog. Spent sometime on it. Glad to learn about the Python library "ShutIt".

Great job man!

Olyboy16:
Hi guys, so i was just playing around with c++, trying to get back on track after a long long time away into Generic GC langs. As a polyglot programmer, its my duty to stay up to date with all my languages.

So , here's the dig. I was playing with algorithms...binary search to be exact. so, i encountered some issues along the way. which actually gave me some serious debug time!
So i thought, why not share the fun....i'm throwing out this challenge to anyone who thinks he's as good a C++ programmer as he/she thinks, to fix this code snippet...don't write your implementation...we all can do that...just /fix?optimize/

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

/**
* Olyboy16; Implementation of a simpler binary search algo
* this algo is limited to O(log n * 2) instead of O(log n)
*/

template<typename T>
string binSearch(vector<int>* hay, const int pin){
	int size = hay->size();
	if(hay->at(size/2) > pin){
		vector<int>* hay2; // if you can eliminate this object...you're good!
		copy(hay->begin(), hay->end(), hay->begin());
		return binSearch<int>(hay2, pin);
	}
	//lets just search through the chop
	auto nd = find(hay->begin(), hay->end(), [=](int& x){
		return x == pin;
	});
	return "[val:"+nd+"]";
}

int main(){
	vector<int>* arr {2,5,6,7,9,5,2,1,89,76,33,56,12,0,98,5,4,3,2,45,654,99};
	sort(arr->begin(), arr->end(), [](int& i, int& j){ //current > later
		return i > j;
	});
	cout << "Finding 86 using binary search! = " << binSearch<int>(arr, 86);
}

Please note that i intentionally designed it to be a recursive solution...its just to pass time really.

What happens when the pin is lesser than than the lenght of the array/2 . And why did you resort to use an ordinary sort rather than implementing the binary search on the second half

WhiZTiM:

Yea... you should check the work he has been pushing out... "Design by Introspection".

BTW, I like the design of your blog. Spent sometime on it. Glad to learn about the Python library "ShutIt".

Great job man!

wao thanks man! i've been discouraged recently to make post cos i dont get any feedbacks, but you just gave me new inspiration! More Posts On The Way.

---

andrei's design by introspection is great, gave me some think time. though i feel like people should have known these law before hand.

---

BTW, pls dont reserve your comments on the bugs on my code, i love being corrected, makes me smarter. i have more codes to post if you dont mind, i deal in AI and i'm trying to create a custom AI-ML. so i've got some pretty interesting code snippets we can brainstorm on.

sharrp:

What happens when the pin is lesser than than the lenght of the array/2 . And why did you resort to use an ordinary sort rather than implementing the binary search on the second half

Hi Sir, please find the correct code on the thread. that code is intentionally buggy.

wao thanks man! i've been discouraged recently to make post cos i dont get any feedbacks, but you just gave me new inspiration! More Posts On The Way.

Ok... I will be checking...!

---

BTW, pls dont reserve your comments on the bugs on my code, i love being corrected, makes me smarter. i have more codes to post if you dont mind, i deal in AI and i'm trying to create a custom AI-ML. so i've got some pretty interesting code snippets we can brainstorm on

Ok.... Its a bit Mathematical... C++ treats its STL comparators with the concept of Strict Weak Ordering. This makes it possible to use a single comparator for A variety of things.

For example. Using the strict Weak Order of < (less than operator). We can establish the following:

- A < B; A is less than B
- B < A; B is less than A
- !(A < B); A is not less than B. Hence, A is greater than or equal to B
- !(B < A); B is not less than A. Hence, B is greater than or equal to A
- !(A < B) && !(B < A); A is neither less than B nor vice-versa, Hence A is equall to B

--------
See how we were able to use one single operator to Cater for others?

- A < B; equivalent to: A < B ; B > A
- B < A; equivalent to: B < A ; A > B
- !(A < B); equivalent to: A >= B ; B <= A
- !(B < A); equivalent to: B >= A ; A <= B
- !(A < B) && !(B < A); equivalent to: A == B

With that knowledge, we can write a generic version of out Binary Search Algorithm. That takes a functor and makes comparison. Recall that the C++'s STL iterator concept uses the notion of One element past the end. Basically, the iterator produced for a range starts out with a closed interval and ends with an Open Interval. Hence, a range is defined as:

    [A, B)  - The first element, A is inclusive; the last element, B is exclusive 

Armed with the above, we could write an iterative version of `binary_search`. Which has similar API with STL's version, but we return an iterator instead of a bool as per C++ STL version.:

namespace tim{
	template<typename Iterator, typename T, typename Compare>
	Iterator binary_search(Iterator first, Iterator last, const T& value, Compare cmp){
		auto sentinel = last;
		while(first != last){
			auto mid = first + std::distance(first, last) / 2;
			//Strict Weak Ordering
			if(!cmp(*first, value) && !cmp(value, *first))
				return first;
			if(!cmp(value, *first) && !cmp(*std::prev(mid), value))
				last = mid;
			else if(!cmp(value, *mid) && !cmp(*std::prev(last), value))
				first = mid;
			else
				return sentinel;
		}
		return sentinel;
	}

	template<typename Iterator, typename T>
	Iterator binary_search(Iterator first, Iterator last, const T& value){
		return tim::binary_search(first, last, value, std::less<T>());
	}
}

Example Usage:

int main(){
	std::vector<int> vec{1,2,3,5,6,6,7,8,9,9,11,22,67,87,98,99,231};

	for(int i = 0; i < vec.size(); i++) std::cout << i << '\t'; std::endl(std::cout);
	for(int a : vec) std::cout << a << '\t';
	for(int k; std::cin >> k, k > -1; ){
		auto iter = tim::binary_search(std::begin(vec), std::end(vec), k);
		if(iter == std::end(vec)){
			std::cout << "Not Found!" << std::endl;
		}
		else{
			std::cout << "Found " << *iter << " at index " << std::distance(std::begin(vec), iter) << std::endl;
		}
	}
	return 0;
}

I haven't run serious tests for the above code though, so, I am still paranoid that there may be a bug lurking somewhere... ...lol

---

Don't mind me... I write libraries, so I am very keen about performance, API intuitiveness and "being generic"... I also answer questions on Stackoverflow...

@whiztim , great job on the code! i see you are a regular c++ customer.
.
.
.
you still dint point out any bug in my own snippet! your code only leverages on mathematical grounds as opposed to my artistic approach. anyway, its great to know i can still find someone that actually writes standard c++ codes on nairaland; i guess i'm a bit rusty on the C++ STL(temporarily).
.
oh and tim, i've checked your github repo. man the 'Value' class is really great! i tried something like that with a mix of c & c++ few years ago, the results were awesome, but not even close to what you've done! good job man, i'll try nd find the header code later to analyze the concept!

*picks up C++ textbook*