1

https://www.youtube.com/watch?v=5xlIPT1FRcA&t=200s

I am struggling to understand how to implement binary search. According to the video, there are 14 numbers in the array. Then he goes on to calculate the midpoint by dividing 14 by 2. What if the user input an odd number, say 15? How can one calculate the midpoint but still follow the instructed pseudo code? The video did not mention anything about odd and even, or there is something I understood wrong? Please help!

Thank you!

3

Even or odd, it doesn't really matter. The point is that you are dividing the list approximately in half, give or take. If the split doesn't occur exactly at the middle (odd number of elements), it can be either the element just before or after the midpoint (even number of elements). Eventually, it will come down to either two elements or 1 elements, assuming the target isn't found at a midpoint.

When the list is split approximately in half, it will eventually keep splitting the list down to that very small number of elements until it either finds the target or determines that it isn't in the ordered list.

BTW, if it is an even number of elements, no element is the exact middle element - there will be one just before and one just after the midpoint. A midpoint element only occurs with an odd number of elements.

If that answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

3
  • So when C calculating the midpoint of an odd number of elements, it will round up I assume? Sorry I am still new to coding. And thank you so much for your help!
    – Thuy
    Apr 26 '17 at 0:10
  • It depends on the code. If it's integer division, it will truncate down. Either way works. Also, an odd number of elements will come out exact. It's even elements that will truncate down. Think about it. 3 elements (1, 2, 3), the midpoint element is 2. For 4 elements (1, 2,3,4), the midpoint could be 2 or 3. Finally, remember that these numbers are the position in the list, not the value of the element in the list.
    – Cliff B
    Apr 26 '17 at 0:47
  • I realize my mistake of saying odd numbers of elements while it's actually the opposite. Thanks for pointing that out. And thanks so much for all the clarifications!
    – Thuy
    Apr 26 '17 at 19:45
0

It doesn't matter odd or even. As long as data type is Integer instead of float, it will take the nearest value.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .