1

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
4

1 回答 1

6

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.

于 2013-03-30T14:58:58.420 回答