function [ target ] = BINARY_search( sorted_values, target_value, MATCH, target_column)
%Binary search algorithm. Works on sorted data with unique values, find values in first or
%supplied columns. 
%
%USAGE: [ target ] = BINARY_search( sorted_values, target_value, MATCH, target_column)
%INPUTS: 
%   sorted_values       : [M*N] array with sorted values, 
%   MATCH               : 0 for exact, 
%                        -1 for the first value equal to or if not found, the index with the value just smaller then the target
%                        -2 for the index with the value just smaller then the target
%                         1 for the last value equal to or if not found, the index with the value just larger then the target
%                         2 for the index with the value just larger then the target
%   target_column    : column to adress.
%OUTPUT
%   target          : array index value, -1 if not found
%
%Tom Schut, 2011
if nargin < 2
    error('Need to supply a sorted list and a target value');
end
if nargin < 3
    MATCH= 0;
end
if nargin < 4
    target_column = 1;
end
if target_column ==1 && (size( sorted_values,1) < size(sorted_values,2))
    sorted_values=sorted_values';
end

target = -1;
low = 1;

high = size(sorted_values,1);  

% Data sorted in ascending fashion
if sorted_values(low,target_column) < sorted_values(high,target_column)
    
    while (target < 0) && (high >= low)
            mid = floor((low+high)/2);

            if sorted_values(mid,target_column) == target_value
                target = mid;
            elseif sorted_values(mid,target_column)> target_value
                high = mid - 1; %search lower half
            else
                low = mid + 1; %search upper half
            end
    end
    if target < 0 %value not exactly found yet
        %NOTE: loop only stops of low > high...
        if MATCH > 0 %find value just larger 
            target = low;   
        elseif MATCH < 0 %find value just smaller
            target = high;
        end 
    %If matching value is found, run through the list to find first or last
    %matching value
    elseif MATCH == 1 %first value equal in sorted list
        while target > 1 && sorted_values(target-1,target_column) == target_value
              target = target-1;   
        end
    elseif MATCH == -1 %last value equal in sorted list
        while target < size(sorted_values,1) && sorted_values(target+1,target_column) == target_value
            target = target+1;             
        end    
    %If matching value is found, run through the list to find first or last
    %non-matching value
    elseif MATCH == 2 %first value just larger in sorted list
        while target < size(sorted_values,1) && sorted_values(target,target_column) == target_value
              target = target+1;   
        end
        
        %no value larger found!
        if sorted_values(target,target_column) == target_value
            target =-1; 
        end
    elseif MATCH == -2 %last value just smaller in sorted list
        while target >1 && sorted_values(target,target_column) == target_value
            target = target-1;             
        end
        %no value smaller found!
        if sorted_values(target,target_column) == target_value
            target =-1; 
        end
    end     
else % Data must thus be sorted in descending fashion    
    
    while (target < 0) && (high >= low)
            mid = floor((low+high)/2);

            if sorted_values(mid,target_column) == target_value
                target = mid;
            elseif sorted_values(mid,target_column)> target_value
                low = mid + 1;%search upper half
            else
                high = mid - 1;%search lower half
            end
    end
    if target < 0 %value not exactly found yet
        %NOTE: loop only stops of low > high...
        if MATCH > 0 %find value just larger 
            target = high;   
        elseif MATCH < 0 %find value just smaller
            target = low;
        end 
    %If matching value is found, run through the list to find first or last
    %matching value
    elseif MATCH == 1 %first value equal in sorted list
        while target < size(sorted_values,1) && sorted_values(target+1,target_column) == target_value
              target = target+1;   
        end
    elseif MATCH == -1 %last value equal in sorted list
        while target > 1 && sorted_values(target-1,target_column) == target_value
            target = target-1;             
        end
    %If matching value is found, run through the list to find first or last
    %non-matching value
    elseif MATCH == 2 %first value just larger in sorted list
        while target > 1 && sorted_values(target,target_column) == target_value
              target = target-1;   
        end
        %no value larger found!
        if sorted_values(target,target_column) == target_value
            target = -1; 
        end
    elseif MATCH == -2 %last value just smaller in sorted list
        while target < size(sorted_values,1) && sorted_values(target,target_column) == target_value
            target = target+1;             
        end
        %no value smaller found!
        if sorted_values(target,target_column) == target_value
            target =-1; 
        end
    end     
end

if target < 1 || target > size(sorted_values,1)
    target = -1;
end