w3hello.com logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML videos Categories
Binary search 1/4 modification

Your formula to determine the pivot is wrong for the 3/4 split. If you want to split an interval between low and high at some point c with 0 <= c <=1, you get:

pivot = low + c * (high - low)
      = (1 - c) * low + c * high

This wil give you low for c == 0, highfor c == 1 and for your 3/4 split:

pivot = 0.75 * low + 0.25 * high

or, with integer arithmetic:

pivot = (3 * low + high) / 4

In particular, the factors for low and high should sum up to 1.

I also think that your function has a logic error: You return the recursion depth, which has no meaning to the array. You should return the pivot, i.e. the array index at which the item is found. That also means that you can't return 0 on failure, because that's a valid array index. Return an illegal index like -1 to indicate that the item wasn't found.





© Copyright 2018 w3hello.com Publishing Limited. All rights reserved.