Binary Search

ilan

ilan

Expert
Licensed User
Longtime User
i just came across binary search and it is very interesting.
i made some simple tests and the result is promising.

i saw a thread by erel about this topic but never put my attention on it now seeing an example on youtube made me a little bit curious.

here is a simple code example (b4j). it will work only on a sorted list. i will need to figure out how it can also work with strings or any kid of object maybe convert obj to bytes -> sort list -> search for the byte and return?? i have not made any tries only with INTEGERS and it works fine. :rolleyes:

B4X: 
#Region Project Attributes
    #MainFormWidth: 600
    #MainFormHeight: 600
#End Region

Sub Process_Globals
    Private fx As JFX
    Private MainForm As Form
    Private myList As List
    Private valueToSearch As Int = 8515600
End Sub

Sub AppStart (Form1 As Form, Args() As String)
    MainForm = Form1
    'MainForm.RootPane.LoadLayout("Layout1") 'Load the layout file.
    MainForm.Show
    myList.Initialize
    
    createList
    
    simpleSearch(myList,valueToSearch)
    binarysearch(myList,valueToSearch)
End Sub

Sub simpleSearch(l As List, value As Int) As Int
    Dim starttime As Long = DateTime.Now
    Dim pos As Int = -1
    For i = 0 To l.Size-1
        If myList.Get(i) = value Then
            pos =1
            Exit           
        End If
    Next
    Log($"Time: ${DateTime.Now-starttime} ms"$)
    Return pos
End Sub

Sub binarysearch(l As List, value As Int) As Int
    Dim starttime As Long = DateTime.Now
    Dim pos As Int = -1
    Dim low=0, middle, high=l.Size-1 As Int
    Do While low <= high
        middle = Floor((low+high)/2)
        If myList.Get(middle) = value Then
            pos = middle
            Exit
        Else if myList.Get(middle) > value Then
            high = middle -1
        Else
            low = middle + 1
        End If
    Loop
    Log($"Time: ${DateTime.Now-starttime} ms"$)
    Return pos
End Sub

Sub createList
    For i = 0 To 10000000
        myList.Add(i)
    Next
End Sub

'Return true to allow the default exceptions handler to handle the uncaught exception.
Sub Application_Error (Error As Exception, StackTrace As String) As Boolean
    Return True
End Sub

RESULTS:

1610272219851.png
 
ilan

ilan

Expert
Licensed User
Longtime User
how does list.indexof(x) works? does it goes the whole list from 0 to list size and check the value or is there a different algorithm running in the background?
 
Erel

Erel

B4X founder
Staff member
Licensed User
Longtime User
List.IndexOf can only work in one simple way, which is to check each one of the items. No one says that the list items are sorted.

If you want to quickly check whether an item exists then use B4XSet. If you want to quickly get an item based on a key then use Map or B4XOrderedMap. They will be faster (for large collections) than binary search.
 
ilan

ilan

Expert
Licensed User
Longtime User
Erel said:
List.IndexOf can only work in one simple way, which is to check each one of the items. No one says that the list items are sorted.

If you want to quickly check whether an item exists then use B4XSet. If you want to quickly get an item based on a key then use Map or B4XOrderedMap. They will be faster (for large collections) than binary search.
Click to expand...

ok, thanks for the hint. btw this is the first time I hear about B4XSet.
usually, I use Maps to store data because it's simple and fast as you mentioned but sometimes a map is not the right tool for me and I use a list or array. anyway, I never have a list bigger than 5000 items so in such small numbers a simple search will be fast enough for me. I just saw that video about binary search and wanted to share it here with the community. maybe someone can find it useful :)

I will definitely have a closer look at B4XSet and B4XOrderedMap!

thank you!
 
rabbitBUSH

rabbitBUSH

Well-Known Member
Licensed User
ilan said:
I just saw that video about binary search
Click to expand...
Maybe you will find this page interesting ( see that they don't have bubble sort in there - if one takes "search" to equate "sort" as a technique )

Searching Alogrithms
 
S

sorex

Expert
Licensed User
Longtime User
ilan said:
i will need to figure out how it can also work with strings
Click to expand...

for such cases linked lists are used often.

you store strings based on the first 2 chars in seperate lists/maps.

if your 8515600 strings only have 241 starting with ab you only need to loop through those 241 to find the right one back.
 
Star-Dust

Star-Dust

Expert
Licensed User
Longtime User
ilan said:
i just came across binary search and it is very interesting.
i made some simple tests and the result is promising.

i saw a thread by erel about this topic but never put my attention on it now seeing an example on youtube made me a little bit curious.

here is a simple code example (b4j). it will work only on a sorted list. i will need to figure out how it can also work with strings or any kid of object maybe convert obj to bytes -> sort list -> search for the byte and return?? i have not made any tries only with INTEGERS and it works fine. :rolleyes:

B4X: 
#Region Project Attributes
    #MainFormWidth: 600
    #MainFormHeight: 600
#End Region

Sub Process_Globals
    Private fx As JFX
    Private MainForm As Form
    Private myList As List
    Private valueToSearch As Int = 8515600
End Sub

Sub AppStart (Form1 As Form, Args() As String)
    MainForm = Form1
    'MainForm.RootPane.LoadLayout("Layout1") 'Load the layout file.
    MainForm.Show
    myList.Initialize
   
    createList
   
    simpleSearch(myList,valueToSearch)
    binarysearch(myList,valueToSearch)
End Sub

Sub simpleSearch(l As List, value As Int) As Int
    Dim starttime As Long = DateTime.Now
    Dim pos As Int = -1
    For i = 0 To l.Size-1
        If myList.Get(i) = value Then
            pos =1
            Exit          
        End If
    Next
    Log($"Time: ${DateTime.Now-starttime} ms"$)
    Return pos
End Sub

Sub binarysearch(l As List, value As Int) As Int
    Dim starttime As Long = DateTime.Now
    Dim pos As Int = -1
    Dim low=0, middle, high=l.Size-1 As Int
    Do While low <= high
        middle = Floor((low+high)/2)
        If myList.Get(middle) = value Then
            pos = middle
            Exit
        Else if myList.Get(middle) > value Then
            high = middle -1
        Else
            low = middle + 1
        End If
    Loop
    Log($"Time: ${DateTime.Now-starttime} ms"$)
    Return pos
End Sub

Sub createList
    For i = 0 To 10000000
        myList.Add(i)
    Next
End Sub

'Return true to allow the default exceptions handler to handle the uncaught exception.
Sub Application_Error (Error As Exception, StackTrace As String) As Boolean
    Return True
End Sub

RESULTS:

View attachment 105843
Click to expand...
A few years ago I wrote about some search algorithms including this one

Search algorithms (and code) on ordered lists

These days I needed an algorithm to quickly search for it on an archive of 280000 strings (sorted alphabetically). So I reckoned that at school I had studied Binary Search. Allows you to find (or ensure that you are not listed) a key with a fixed and minimum access to the archive. Access...
www.b4x.com www.b4x.com
 
ilan

ilan

Expert
Licensed User
Longtime User
sorex said:
for such cases linked lists are used often.

you store strings based on the first 2 chars in seperate lists/maps.

if your 8515600 strings only have 241 starting with ab you only need to loop through those 241 to find the right one back.
Click to expand...

nice idea. but the code will be a little bit messy when dealing with so many lists.
anyway, i don't have such problems. my list aren't that big :) but it is good to know ways how you could solve such issues!
 
E

emexes

Expert
Licensed User
ilan said:
figure out how it can also work with strings
Click to expand...
Change the value type from int to string (or other number type) and it should still work fine. As long as you can compare whether two values are equal or which one is bigger, the algorithm works.

or any kind of object maybe convert obj to bytes
Click to expand...
? Correct. The sorted ordering of those objects will look random to human eyes but again, as long as you can compare two objects and determine if they are "equal" (ie all bytes are the same) or which one is "bigger" (ie, for the first byte that differs, which one has the higher value), the algorithm works.
 
You must log in or register to reply here.
Top