Modify Binary Search in C++: fails when target value is immediately before midpoint of array

[PennyMew]

The C++ Binary Search example fails for any input where the target value is immediately before the midpoint of array. (When the value is at v[v.size()/2-1]).

Here are some example inputs that fail (returning false when true would be expected):

• "1, 2" "1"
• "1, 2, 3" "1"
• "1, 2, 3, 4" "2"
• "1, 2, 3, 4, 5" "2"
• "1, 2, 3, 4, 5, 6" "3"
• "1, 2, 3, 4, 5, 6, 7" "3"

For the given example "1, 2" "1", the code does the following:

• before the while loop:
  • start = 0
  • end = 2
• while loop condition start < end is true, so we enter the while loop:
  • mid = 1
  • v[1] is 2, which greater than target num==1, so we set end=mid-1, which is end==0
• while loop condition start < end is now false, because start==1 and end==1, so we exit the while loop
• the search target was not found, so we return "false"

To fix it:

end is an exclusive range limit, not inclusive, so setting end=mid-1 effectively skips an index.

line 94 ought to be end=mid and not end=mid-1.

https://github.com/TheRenegadeCoder/sample-programs/blob/beec51fe10378beacb422a62a774eb7a34075125/archive/c/c-plus-plus/binary-search.cpp#L88-L101

I'd recommend adding one of these failing example inputs as a test case for all binary search implementations in all languages, since this is an algorithmic issue that could appear in any language.

[jrg94]

Nice call! The testing should be easy to add. I'll get around to it (or if someone wants to jump on it first).

[AjayMaheshwari23]

@PennyMew i can make the necessary changes , can you assign it to me .

[jrg94]

I think @araihC is taking care of the actual program if you want to fix the testing, @AjayMaheshwari23 .

[AjayMaheshwari23]

i guess code is fixed by @PennyMew 3 days ago , so @jrg94 you can close this issue . if not do let me know

[jrg94]

I don't believe this test case was ever added. If you'd like to add it, that would help!

[AjayMaheshwari23]

Can you guide me a bit how to fix the testing part or add new test cases . provide any article link or something which I can refer .

[jrg94]

Yes! The binary search test file is here: https://github.com/TheRenegadeCoder/sample-programs/blob/main/test/projects/test_binary_search.py

You should be able to get a feel for how it works. If not, let me know. If I understand correctly, we basically need to add one more test case which handles that pesky midpoint error.