Find in sorted array

4D v15


Find in sorted array ( array ; valor ; > ou < {; posPrim {; posUlt}} ) -> Resultado

Parâmetro	Tipo	Descrição
array	Array	Array a buscar
valor	Expression	Valor do mesmo tipo a buscar no array
> ou <	Operador	> se array é ordenado em ordem ascendente, < se é ordenado em ordem descendente
posPrim	Inteiro longo	Posição de sua primeira ocorrência se for encontrado o valor; caso contrário a posição onde deveria ser inserido o valor
posUlt	Inteiro longo	Posição de sua última ocorrência se não se encontra o valor; caso contrário igual posPrim
Resultado	Booleano	True se pelo menos um elemento no array coincide com o valor, False em caso contrário

Descrição

Tema: Arrays

O novo comando Find in sorted array devolve true se pelo menos um elemento no array ordenado com o valor e opcionalmente devolve a posição dos elementos correspondentes. Diferente de Find in array, Find in sorted array só funciona com um array ordenado e oferece informação sobre a posição das ocorrências, o que lhe permite inserir elementos se for necessário.

O array deve estar já ordenado e deve coincidir com a ordem específica pelo parâmetro > ou < (ou seja, o símbolo "maior que" para a ordem ascendente e o símbolo "menor que" para a ordem descendente). O comando Find in sorted array tomará vantagem da ordem e uso de um algoritmo de ´pesquisa binária, que é bem mais eficiente para grandes arrays (para mais informação, consulte a página algoritmo de pesquisa binária em Wikipédia). No entanto, se o array não está ordenado corretamente, o resultado pode ser incorreto.

O comando ignorará a indicação de ordem se comporta como um Find in array (pesquisa sequencial, devolvendo -1 para posPrim e posUlt se não se encontra o valor) em qualquer dos seguintes casos:

se o tipo de array não pode ordenar (por exemplo arrays ponteiro),
se o array é de tipo booleano (não preciso),
se a base de dados não é Unicode (modo compatibilidade) e o array é uma cadeia ou array texto,
quando é procurado em um array text para uma cadeia que inclui um coringa ('@') no começo ou no meio da cadeia (utilizando uma pesquisa binária com um caractere coringa não é possível porque os elementos correspondentes podem não ser contínuos no array).

Em caso de que o comando devolva False, o valor devolvido em posPrim pode ser passado a INSERT IN ARRAY para inserir o valor no array mantendo o array ordenado. Esta sequencia é mais rápida que a inserção de um novo elemento ao final do array e logo chamar a SORT ARRAY para mover ele ao lugar correto.

O valor devolvido em postUlt pode ser combinado com o valor devolvido em posPrim para realizar sobre cada elemento do array que coincida com o valor (sob um For...End for) ou para encontrar o número total de ocorrências (como encontraria o comando Count in array mais rápido).

Exemplo 1

Você deseja inserir um valor, se for necessário, mantendo o array ordenado:

 C_LONGINT($pos)

 If(Find in sorted array($array ;$value ;>;$pos)

    ALERT("Found at pos "+String($pos))

 Else

    INSERT IN ARRAY($array ;$pos)

    $array{$pos}:=$value

 End if

Exemplo 2

Você quer encontrar o número de ocorrências das cadeias que começam por "test" e criar uma cadeia que vincula todos estes elementos:

 C_LONGINT($posFirst ;$posLast)

 C_TEXT($output)

 If(Find in sorted array($array ;"test@";>;$posFirst ;$posLast))

    $output:="Found "+String($posLast-$posFirst+1)+" results :\n"

 End if

 For($i ;$posFirst ;$posLast)

    $output:=$output+$array{$i}+"\n"

 End for