Android Code Snippet Find position of value in a list (Or Not)

Modified 21/9/2017: see below.

SubName: FindPositionNum, FindPositionStr

Description:

We can find the index for an item we know is in a list by using indexOf on the list, but how do you find the next or previous item when the target may not be in the list.

This code uses a binary chop to find the exact or the next or previous item in a sorted list.

There are two subroutines, one for numbers and one for strings.

Numbers:

'Find the exact, previous or next number in a sorted list of numbers
'Higher = True for the next highest (Returns -1 if there are no higher items in the list)
'or False for the next lowest (Returns -1 if there are no lower items in the list).
'Returns the index in the list of the required hit
Public Sub FindPositionNum(Target As Object, L As List, Higher As Boolean) As Int
    Dim iMax,iMin,iMid As Int
    iMax=L.Size-1
    iMin=0
    'Set up for first iteration
    iMid=iMin+((iMax-iMin)/2)
    Dim Val As Object = L.get(iMid)

    'Start
    Do While iMin < iMax
        '1st or second half
        If Val < Target Then
            iMin=iMid+1
        Else
            iMax=iMid
        End If
        'Set pointer to half way for next iteration
        iMid=iMin+((iMax-iMin)/2)
        Val = L.get(iMid)
    Loop

    If Higher Then
        If Target > Val Then
            Return -1
        Else
            Return iMid
        End If
    Else
        If Val > Target Then
            Return iMid - 1
        Else
            Return iMid
        End If
    End If
End Sub

Strings:

'Find the exact, previous or next String in a sorted list of Strings
'Higher = True for the next highest (Returns -1 if there are no higher items in the list) 
'or False for the next lowest (Returns -1 if there are no lower items in the list).
'Returns the index in the list of the required hit
Sub FindPositionStr(Target As String, L As List, Higher As Boolean) As Int
    Dim iMax,iMin,iMid As Int
    iMax=L.Size-1
    iMin=0
    'Set up for first iteration
    iMid=iMin+((iMax-iMin)/2)
    Dim Val As String = L.get(iMid)

    'Start
    Do While iMin < iMax
        '1st or second half
        If Val.CompareTo(Target) < 0 Then
            iMin=iMid+1
        Else
            iMax=iMid
        End If
        'Set pointer to half way for next iteration
        iMid=iMin+((iMax-iMin)/2)
        Val = L.get(iMid)
    Loop

    If Higher Then
        If Target.CompareTo(Val) > 0 Then
            Return -1
        Else
            Return iMid
        End If
    Else
        If Val.CompareTo(Target) > 0 Then
            Return iMid - 1
        Else
            Return iMid
        End If
    End If
End Sub

Example Usage:

    'Ints
    Dim L As List
    L.Initialize
    L.AddAll(Array As Int(1651,21,3568,5123,9997,1,15000,11325,2568))
    L.Sort(True)

    Dim Target As Int = 11399

    Log(L.Get(FindPositionNum(Target,L,True)))

    'Doubles

    Dim L As List
    L.Initialize
    L.AddAll(Array As Double(1651,21,3568,5123,9997,1,15000,11325,2568))
    L.Sort(True)

    Dim TargetD As Double =  25.767

    Log(L.Get(FindPositionNum(TargetD,L,False)))

    'Bytes

    Dim L As List
    L.Initialize
    L.AddAll(Array As Byte(0x0A,0x5F,0xB9,0xDF,0x20,0xF0,0xFF))
    L.Sort(True)

    Dim TargetB As Byte = 0xC2

    'Display as Hex
    Dim Format As JavaObject

    'Format String for output
    Format.InitializeStatic("java.lang.String")
    Dim FormatStr As String = "%#4X"
    'Get the result
    Dim Data() As Object = Array As Object(L.Get(FindPositionNum(TargetB,L,True)))
    'Display the result
    Log(Format.RunMethod("format",Array As Object(FormatStr,Data)))

    'Strings

    Dim L As List
    L.Initialize

    L.AddAll(Array As String("Apple","Plum","Orange","Date","Bananna"))
    L.Sort(True)

    Dim TargetStr As String =  "Lemon"

    Log(L.Get(FindPositionStr(TargetStr,L,True)))

For a real life example, I was searching a time list index to see when the next event was due after an arbitrary time.

One thing it can't do is return a position higher than the size of the list, so if your target is after the end of the list, even if you ask for a higher hit, it will return the last entry. You will probably want to test for that before calling this sub.

Modified the above behaviour, now returns -1 if Higher is selected and there is no higher items in the list. Also returns -1 if higher is false and there are no lower values in the list. This is more in line with the standard IndexOf methods.

If Target > L.Get(L.Size - 1) Then
    'Do whatever
Else
    'Call the sub
    Log(L.Get(FindPositionNum(TargetD,L,False)))
End If

Tags: Find position in List Binary Chop Search

 

[stanks]

why list of strings should be sorted? is it possible to use this code for unsorted list (didn't try it)?

 

[udg]

Hi stanks,

you need an ordered list to apply the binary search.
Reading the code you can easily see that on each loop the algorythm chooses the appropriate half of the list (elements greater or lesser than the one currently under test). This should be the fastest algorythm to search an element in an ordered list.

Umberto

 

[stevel05]

Modified to behave more like the standard IndexOf methods.