CODEWITHSUNDEEP
f#
Josh Buedel
Josh Buedel

Reputation: 1863

Why doesn't this binary_search function return 5?

This f# program does a binary search on an int array to find the first occurrence of a number. Once it finds the number it prints the position and then returns it. Then it prints the return value, but prints a different number. I expected the same number. Why is it different?

let int_array = [| 1; 3; 3; 4; 4; 5; 5; 6; 6; 6; 6; 6; 6; 6; 6; 6; 6; 6; 8; 9|]

let binary_search target (array:int[]) = 
    let rec bsearch found_pos start_i end_i  =
        let mid_i = start_i + (end_i-start_i) / 2
        if start_i = end_i then
            printfn "answer is %d" found_pos
            found_pos
        elif array.[ mid_i ] = target then
            bsearch mid_i start_i mid_i-1 
        elif array.[ mid_i ] < target then
            bsearch found_pos (mid_i+1) end_i
        else
            bsearch found_pos start_i (mid_i-1)
    bsearch -1 0 ((Array.length array)-1)


let ans = binary_search 5 int_array
printfn "but it returns %d" ans

Here is the output:

answer is 5
but it returns 3

Upvotes: 1

Views: 138

Answers (1)

svick
svick

Reputation: 244767

Your problem is missing parentheses. The code bsearch mid_i start_i mid_i-1 is the same as (bsearch mid_i start_i mid_i)-1. If you change it to bsearch mid_i start_i (mid_i-1), the first and final results will be the same.

Upvotes: 6

Related Questions