CODEWITHSUNDEEP
pythonalgorithmbinary-search
haneulkim
haneulkim

Reputation: 4928

In binary search, how does computer choose mid point and when there is only two elements left

I've read some stackoverflow questions and other blogs about this matter.

Most of them explain to choose mid point by using:

1. low + (high - low)/2
2. (low + high)/2, round down to integer.

from Deciding mid in binary search and https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search

None of them quite make sense.

say I have a list in the form 

lst = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

using 1. midpoint = 46.5 and by using 2. midpoint = 50.5, rounded down to 50.

both midpoint isn't even in my list.

Furthermore when there are only 2 element, which one does it choose as a midpoint?

Upvotes: 2

Views: 2725

Answers (3)

amanuel teferi
amanuel teferi

Reputation: 26

  1. low and high refer to the indexes of the list not the values of them

  2. if there are two elements it would take the low and the high which will be 0 and 1 and then do low + (high - low)/2 which would equal to 0 + (1 - 0)/2 which gives us 0.5 depending on your algorithm you can round up or round down, since you have chosen rounding down we have a value of 0 which will be the index of the middle point that will be chosen

Upvotes: 1

MBo
MBo

Reputation: 80187

Binary search low/high refers to ndexes rather than array values.
So in your case mid index is (0+9)/2=4.

In case of length 2 you'll get mid index 0, right part will have one element, left is empty (or contains the only 0-th element, if mid is not treated separately).

Upvotes: 2

Sultan Singh Atwal
Sultan Singh Atwal

Reputation: 820

The low and the high variables do not refer to the elements of the list or the array. They refer to the indices of the list or array. So the middle element will not be given by: low + (high - low)/2 or (low + high)/2 (round down to an integer) but rather by lst[low + (high - low)/2] or lst[(low + high)/2]

Upvotes: 3

Related Questions