Forum Discussion

FunnyPanda's avatar
FunnyPanda
New Member
2 years ago

Binary Search for Power Query | List.Contains alternative

Hi there!

I've been struggling with validation that I needed to perform on some data and I hope this might help someone.
Problem: check if a large non sequential list contains some number with the expected outcome being true or false.


YouTube suggested me this video where they talk about what is Binary Search and I tried it and to my amusement it worked.
The previous query ran for 4 hours and by implementing this instead of List.Contains, the run time reduced to 1h25minutes!

As they say on the video, the list must be sorted in a ascending order.

 

 

let
    f=
        (_list as list, _x as any, _t as number, _b as number) as logical =>
            if _t>_b then false else
            let
                _m = Number.Round((_t+_b)/2,0)
            in 
                if _x<_list{_m} then @f(_list, _x, _t, _m-1) else
                if _x>_list{_m} then @f(_list, _x, _m+1, _b) else
                true
in
    f

 

 

 

I also did a limited test with text and it seemed to work.

2 Replies

    • FunnyPanda's avatar
      FunnyPanda
      New Member

      It ran with the list buffered.
      I didn't run any tests with an unbuffered list.