[Dormilich]

Hi,

I wonder what is a good algorithm to find a specific value in an already sorted array (I know that I could simply loop through the array, but that’s not efficient …).

maybe an example will help to explain that better:

let’s assume there is a data array [1, 2, 3, 5, 8, …] (the application will store objects, but for the sake of simplicity I use integers here), then I want to find those two numbers, which are closest to my input number, i.e. if the input is 3.4 it should return 3 & 5 (respectively the array indices thereof). I thought the algorithm could be something kinda like Quicksort (without the actual sorting) but I’m not sure about that.

Dormi

PS. the application language is Javascript

[macosxnerd101]

Take a look at Binary Search. It partitions the array into halves into sub-sections based on the relation of the value you are searching for to the elements in the array. Even if the element isn't found, it can be used to tell you where it should be located.

[calebjonasson]

In addition to macosxnerd101's comment, this is also the ideal way to manually sort an array of information.

[Luckless]

you might also find Map(direct access/no searching) useful. I know javascript doesn't have a Map, but from what I understand, Objects can be assigned properties on the fly.

//not my own example... Taken from other source
var object = new Object();
object.abc = "123";

//can be retrieved with
object.abc

this might be useful to you since you already know what you are looking for (known as a key). If you try to retrieve the key, a value assigned to it will be returned. Just spewing ideas

[macosxnerd101]

It's almost not worth the time it takes to implement a Map if one doesn't already exist. The advantages of a Map or HashTable is the use of a hashing algorithm, which allows for O(1) insertion, lookup, and modification of elements.

[Luckless]

haha true, but it would work I'd personally go with the binary search in this case

[Dormilich]

I went with the Binary Search, it’s only 300 datasets to read from a CSV file, and I don’t like numeric object keys.

for those interested in the implementation

var data = [];

data.binarySearch = function (key, value)
{
	if (isNaN(value)) {
		throw new TypeError("Viscosity is not a Number");
	}
	value = parseFloat(value);
	var c, min = 0, max = this.length - 1; 
	function dataOf(i)
	{ 
		return data[i][key];
	}
	// check bounds
	if (dataOf(min) > value) {
		throw new Error("Value too small");
	}
	if (dataOf(max) < value) {
		throw new Error("overflow");
	}
	do {
		// abort condition
		if ((max - min) < 2) {
			return Viscosity.createIntermediate(this[min], this[max], value);
		}
		c = Math.ceil((max + min) / 2);
		
		if (dataOf(c) > value) {
			max = c;
		}
		else if (dataOf(c) < value) {
			min = c;
		}
	} while (dataOf(c) != value);
	
	return this[c];
};

This post has been edited by Dormilich: 24 May 2011 - 01:33 PM

[AdamSpeight2008]

There is a potentially quicker convering algorithm, based on ratios.

I think I've coded it correctly, if not is something very similar.

Function Find(Value,Min,Max)
Offset=Min
Delta = A[Max] - A[Min]
Count = Max - Min
Targe = Value / Delta
Index = Targe  * Count + Offset
cmp = A[Index].ComparedTo(Value)
If cmp=0 Then Return Index
If Min=>Max Then Return -1

If cmp>0 Then Return Find(Min,Index)
If cmp<0 Then Return Find(Index,Max)
End Function

This post has been edited by AdamSpeight2008: 25 May 2011 - 04:05 PM

[Dormilich]

that actually fared worse than the binary search for smaller (10,000 elements) arrays. (I think that’s due to the rounding required on line #7, so in the worst case, the lower bound is repeatedly iterated until it switches to the upper bound)

This post has been edited by Dormilich: 26 May 2011 - 02:30 AM

[AdamSpeight2008]

I've had time to implement a working version.

  Module Module1

    Sub Main()
    Dim a0() As Integer = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
    Dim a1() As Integer = {0, 1, 1, 2, 2, 3, 3, 4, 5, 5}
    Dim a2() As Integer = {0, 5, 8, 9, 10, 11, 12, 14, 15, 16}
    Dim i1 = Find(a2, 5, 0, 9)
    End Sub

   Private Function Find(ByRef ar As Integer(), Target As Integer, I_min As Integer, I_max As Integer, Optional depth As Integer = 0) As Integer
    Dim I_delta As Integer = I_max - I_min
    ' There must be at least one item in the collection.
    If I_delta < 1 Then Return -1
    ' Calculate the abosulate value of the minimum value.
    Dim V_offset = Math.Abs(ar(I_min))
    ' Work out the delta between the max and min values, accounting for the offset.
    Dim V_delta As Integer = (ar(I_max) + V_offset) - (ar(I_min) + V_offset)
    ' What
    Dim Percentage As Double = ((Target + V_offset) / (V_delta))
    ' Is the ratio not within the bound 0 to 1, if so then return -1 (Not Found)
    If Percentage > 1 OrElse Percentage < 0 Then Return -1
    ' Calcluate the Index position of the guess.
    Dim I_Guess = Math.Floor(I_min + (I_delta * Percentage))
    ' What value is at the guess index.
    Dim V_Guess = ar(I_Guess)
    ' Compate the guess value with the target
    Dim cmp = V_Guess.CompareTo(Target)
    Select Case cmp
      Case 0 : Return I_Guess + I_min
      Case Is < 0 : Return Find(ar, Target, I_Guess+1,  I_max - 1, depth + 1)
      Case Else
        Return Find(ar, Target, I_min + 1, I_Guess-1, depth + 1)
    End Select
  End Function



End Module

Worse Case: O(n)
Best Case: O(ln ln n)
Edit: Modified the code so the algorithm converges correctly.

This post has been edited by AdamSpeight2008: 27 May 2011 - 06:27 AM

[baavgai]

Hmm... if we're on optimizations, I saw a minor one:

while(true) {
	if ((max - min) < 2) { return Viscosity.createIntermediate(this[min], this[max], value); }
	var c = Math.ceil((max + min) / 2);
	var foundValue = dataOf(c);
	if (foundValue==value) { return this[c]; }
	if (foundValue > value) {
		max = c;
	} else {
		min = c;
	}
}

This saves two array lookups and one comparison. Might be a noticeable improvement on larger sets.

[AdamSpeight2008]

Array lookups are constant time.

[AdamSpeight2008]

In the algorithm I post.
If the contents of the array are linear, then the lookup (assuming that it is within the set) is O(1).

[baavgai]

Frankly, I'm not looking at your algorithm. I was responding the to OP's post in the language in question. It's irrelevant that array lookups are constant time; eliminating one makes that constant zero, which is reasonably better than whatever time it takes.

This post has been edited by baavgai: 27 May 2011 - 06:48 AM

[AdamSpeight2008]

Nemerle Version. (Returns a tuple of Boolean Int32) ie Was it found? Index / insertion index.

  Find (  ar : array [Int32],
      target : Int32,
       I_min : Int32,
       I_max : Int32
     ) :  Boolean * Int32
{ def I_delta = I_max - I_min;
  match( I_delta < 1 )
  { |  true =>  ( false, I_min )
    | false =>
    { def V_offset = Math.Abs(ar[I_min]);
      def V_delta = ar[I_max] - ar[I_min]; 
      def p  = (target:double + V_offset) / V_delta;
      match (p)
      { | p when p<0  => ( false, I_max + 1 )
        | p when p>1  => ( false, I_min     )
        | _           =>
          def I_guess  = Math.Floor(I_delta * p + V_offset):>Int32;
          def V_guess = ar[I_guess];
          def cmp = V_guess.CompareTo(target);
          match (cmp)
          { | 0          => ( true, I_guess );
            | p when p<0 => Find(ar, target, I_guess + 1, I_max - 1);
            | _          => Find(ar, target, I_min + 1, I_guess - 1);
          }
      }
    }
  }
}

This post has been edited by AdamSpeight2008: 27 May 2011 - 08:16 AM