By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,814 Members | 1,671 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,814 IT Pros & Developers. It's quick & easy.

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

P: 12
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:

Expand|Select|Wrap|Line Numbers
  1. public static Comparable linearSearch (Comparable[] list, Comparable target)
  2.    {
  3.       int index = 0;
  4.       boolean found = false;
  5.  
  6.       while (!found && index < list.length)
  7.       {
  8.          if (list[index].equals(target))
  9.             found = true;
  10.          else
  11.             index++;
  12.       }
  13.  
  14.       if (found)
  15.          return list[index];
  16.       else
  17.          return null;
  18.    }
  19.  
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).
May 4 '08 #1
Share this Question
Share on Google+
3 Replies


Ganon11
Expert 2.5K+
P: 3,652
You might be able to write a private helper function that searches for an item starting at a position given as an argument:

Expand|Select|Wrap|Line Numbers
  1. public static Comparable linearSearch (Comparable[] list, Comparable target, int start)
It would be nearly identical to your current code. In fact, you can change the original function to this:

Expand|Select|Wrap|Line Numbers
  1. public static Comparable linearSearch (Comparable[] list, Comparable target) {
  2.    return linearSearch(list, target, 0);
  3. }
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.
May 4 '08 #2

Expert 10K+
P: 11,448
Compare the above with the String.indexOf(String str, int fromIndex) method.

kind regards,

Jos
May 5 '08 #3

10K+
P: 13,264
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

Expand|Select|Wrap|Line Numbers
  1. static int indexOf(char[] source, int sourceOffset, int sourceCount,
  2.                        char[] target, int targetOffset, int targetCount,
  3.                        int fromIndex) {
  4.     if (fromIndex >= sourceCount) {
  5.             return (targetCount == 0 ? sourceCount : -1);
  6.     }
  7.         if (fromIndex < 0) {
  8.             fromIndex = 0;
  9.         }
  10.     if (targetCount == 0) {
  11.         return fromIndex;
  12.     }
  13.  
  14.         char first  = target[targetOffset];
  15.         int max = sourceOffset + (sourceCount - targetCount);
  16.  
  17.         for (int i = sourceOffset + fromIndex; i <= max; i++) {
  18.             /* Look for first character. */
  19.             if (source[i] != first) {
  20.                 while (++i <= max && source[i] != first);
  21.             }
  22.  
  23.             /* Found first character, now look at the rest of v2 */
  24.             if (i <= max) {
  25.                 int j = i + 1;
  26.                 int end = j + targetCount - 1;
  27.                 for (int k = targetOffset + 1; j < end && source[j] ==
  28.                          target[k]; j++, k++);
  29.  
  30.                 if (j == end) {
  31.                     /* Found whole string. */
  32.                     return i - sourceOffset;
  33.                 }
  34.             }
  35.         }
  36.         return -1;
  37.     }
Sun Microsystems code
May 5 '08 #4

Post your reply

Sign in to post your reply or Sign up for a free account.