LinearSearch in Java with two of the same object (type).

[JinFTW]

Hey guys I was just curious as to how (if) you could use linearsearch to find two of the same item in an array. For example:

public static Comparable linearSearch (Comparable[] list, Comparable target)
   {
      int index = 0;
      boolean found = false;

      while (!found && index < list.length)
      {
         if (list[index].equals(target))
            found = true;
         else
            index++;
      }

      if (found)
         return list[index];
      else
         return null;
   }

I realize this will only give me the first occurence of the object, but I wasn't sure of how I'd start to look for the second (if it exists).

[Ganon11]

You might be able to write a private helper function that searches for an item starting at a position given as an argument:

[CODE=java]public static Comparable linearSearch (Comparable[] list, Comparable target, int start)[/CODE]

It would be nearly identical to your current code. In fact, you can change the original function to this:

[CODE=java]public static Comparable linearSearch (Comparable[] list, Comparable target) {
return linearSearch(li st, target, 0);
}[/CODE]

with some extra trickery.

In essence, you would search for the target item, then search for it again starting at the index after this first occurence.

[JosAH]

Compare the above with the String.indexOf( String str, int fromIndex) method.

kind regards,

Jos

[r035198x]

Compare the above with the String.indexOf( String str, int fromIndex) method.

kind regards,

Jos

If the values are Strings of course. If you want to use the idea behind that method posted above by Jos for non Strings, then here's the implementation of the method

[CODE=java]static int indexOf(char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}

char first = target[targetOffset];
int max = sourceOffset + (sourceCount - targetCount);

for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
if (source[i] != first) {
while (++i <= max && source[i] != first);
}

/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
for (int k = targetOffset + 1; j < end && source[j] ==
target[k]; j++, k++);

if (j == end) {
/* Found whole string. */
return i - sourceOffset;
}
}
}
return -1;
}[/CODE] Sun Microsystems code