Tips for implementing binary search (Chapter 11 Java edition)

**programmer99** · October 16, 2017, 10:41pm

In EPI Java the first half of chapter 11 are variations of binary search implementations. They are actually surprisingly difficult. What are some tips for determining if I should have while(left<right) or while(left<=right). Or whether I should set Left to mid+1 or just mid. Or whether I should have three clauses to check for >mid, <mid, ==mid or just two clauses <mid, >=mid. I’m just running into a lot of off by one errors and having a hard time identifying edge cases. And I cant find any good resources online for how to implement variations on binary-search.

**lgtout** · October 17, 2017, 1:11am

Which version of EPIJ? Because, my version (1.6.1) chapter 11 is “Heaps”.

**programmer99** · October 17, 2017, 1:31am

Where do you find the version

**lgtout** · October 17, 2017, 2:16am

It’s on the back of the first page in the book, after the cover.
What’s the title of chapter 11 in your version?

**programmer99** · October 17, 2017, 4:20am

Searching is the name of the chapter

**lgtout** · October 17, 2017, 4:50pm

Are you doing the variant problems too? Have you gone over the solutions provided in the book? If so, do they not provide the insight you’re looking for?

As for corner cases, you can see if my test cases provide the coverage you’re looking for. I’ve completed the first 6 problems, including variants. The tests are here (in Kotlin).

I don’t know of any general rules for adapting binary search, other than the textbook binary search algorithm. This is probably because there are many forms that adaptation can take. So far, I’ve made progress by applying experimentation, persistence, practice, and patience. Keep at it, and you’ll see you’ll develop the intuitions naturally.

It may be helpful to set the problems aside for a bit, implement standard binary search, and play with it like a toy. By that I mean, without any specific goal in mind, making small modifications and seeing what effect it has on the output.

**programmer99** · October 17, 2017, 5:07pm

Thanks for the test cases lgtout that should be helpful

**programmer99** · October 17, 2017, 5:07pm

I guess whats confusing me a lot is whether or not to use < or <= as a comparison of the left and right indices

**lgtout** · October 17, 2017, 5:21pm

What’re you using the comparison to do? Is it to know when to break out of the search?

**programmer99** · October 17, 2017, 9:13pm

Actually after looking through the solutions more deeply they are making alot more sense today

**lgtout** · October 17, 2017, 9:40pm

that’s awesome!