-6

I'm really only looking for pseudo code here.

I'm trying to write a binary search algo which finds the location of a value in a series of values (or the location of where a value should be in a series when the value doesn't exist).

I'm getting hung up on rounding when the amount of values in a series is odd. I'm not sure if I should round up, down or both or one way in some cases or another in another.

Example data: 1,2,3,5,6,7,8

Need to correctly return location for '4', '7', '9'.

  • 1
    Am down voting this question.You kindly requested to post in the other community – quintumnia Jun 6 '17 at 10:35
  • Not on StackOverflow, please. – Basilevs Jun 6 '17 at 11:08
  • @Basilevs ,Guide our fellow ;cross validated/artificial intelligence but then the OP needs to revise the question.Effectively before posting it there!! – quintumnia Jun 6 '17 at 11:35
0

When partitioning your set of values, it does not matter which of the two halves the odd element ends up in. The very worst that could happen is that the element you are looking for consistently happens to be in the larger partition, which means that you will need one comparison more than the best case (where the element is consistently in the smaller partition).

You can easily test this yourself by repeatedly partitioning an example data set and seeing what the effect of the rounding choice is.

For example, with consistently rounding down, you would get these partitions for you 7-element data set

|1 2 3 5 6 7 8|
|1 2 3|5 6 7 8|
|1|2 3|5 6|7 8| <- first element in a partition by its own
|1|2|3|5|6|7|8| <- all elements in a partition by themselves

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.