Skip to content

Instantly share code, notes, and snippets.

@sentientmachine

sentientmachine/gist:68deacc4ec7e710f968a3c8e269bbee2

Created May 31, 2022 17:35
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sentientmachine/68deacc4ec7e710f968a3c8e269bbee2 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sentientmachine/68deacc4ec7e710f968a3c8e269bbee2 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. sentientmachine created this gist May 31, 2022.
    80 changes: 80 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,80 @@
    function success = main()
    a = ["hello"; "unsorted"; "world"; "moobar"]
    b = cellstr(a)
    find(ismember(b, 'world')) %returns 3

    function i = binsearch(array, val, low, high)
    %binary search algorithm for numerics, Usage:
    %myarray = [ 30, 40, 50.15 ]; %already sorted list
    %binsearch(myarray, 30, 1, 3) %item 30 is in slot 1
    if ( high < low )
    i = 0;
    else
    mid = floor((low + high) / 2);
    if ( array(mid) > val )
    i = binsearch(array, val, low, mid-1);
    elseif ( array(mid) < val )
    i = binsearch(array, val, mid+1, high);
    else
    i = mid;
    endif
    endif
    endfunction

    function i = binsearch_str(array, val, low, high)
    % binary search for strings, usage:
    %myarray2 = [ "abc"; "def"; "ghi"]; #already sorted list
    %binsearch_str(myarray2, "abc", 1, 3) #item abc is in slot 1
    if ( high < low )
    i = 0;
    else
    mid = floor((low + high) / 2);
    if ( mystrcmp(array(mid, [1:end]), val) == 1 )
    i = binsearch(array, val, low, mid-1);
    elseif ( mystrcmp(array(mid, [1:end]), val) == -1 )
    i = binsearch_str(array, val, mid+1, high);
    else
    i = mid;
    endif
    endif
    endfunction
    function ret = mystrcmp(a, b)
    %this function is just an octave string compare, it's exactly like
    %strcmp(str1,str2) in C, or java.lang.String.compareTo(...) in Java.
    %returns 1 if string a > b
    %returns 0 if string a == b
    %return -1 if string a < b
    letters_gt = gt(a, b); %list of boolean a > b
    letters_lt = lt(a, b); %list of boolean a < b
    ret = 0;
    %octave makes us roll our own string compare because
    %strings are arrays of numerics
    len = length(letters_gt);
    for i = 1:len
    if letters_gt(i) > letters_lt(i)
    ret = 1;
    return
    elseif letters_gt(i) < letters_lt(i)
    ret = -1;
    return
    endif
    end;
    endfunction

    %Assuming that myarray is already sorted, (it must be for binary
    %search to finish in logarithmic time `O(log-n))` worst case, then do

    myarray = [ 30, 40, 50.15 ]; %already sorted list
    binsearch(myarray, 30, 1, 3) %item 30 is in slot 1
    binsearch(myarray, 40, 1, 3) %item 40 is in slot 2
    binsearch(myarray, 50, 1, 3) %50 does not exist so return 0
    binsearch(myarray, 50.15, 1, 3) %50.15 is in slot 3

    myarray = [ 9, 40, -3, 3.14, 20 ]; %not sorted list
    myarray = sort(myarray)

    myarray2 = [ "the"; "cat"; "sat"; "on"; "the"; "mat"]; %not sorted list
    myarray2 = sortrows(myarray2)
    end