1 //******************************************************************************
2 //
3 // File: Searching.java
4 // Package: edu.rit.util
5 // Unit: Class edu.rit.util.Searching
6 //
7 // This Java source file is copyright (C) 2011 by Alan Kaminsky. All rights
8 // reserved. For further information, contact the author, Alan Kaminsky, at
9 // ark@cs.rit.edu.
10 //
11 // This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
12 // software; you can redistribute it and/or modify it under the terms of the GNU
13 // General Public License as published by the Free Software Foundation; either
14 // version 3 of the License, or (at your option) any later version.
15 //
16 // PJ is distributed in the hope that it will be useful, but WITHOUT ANY
17 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
18 // A PARTICULAR PURPOSE. See the GNU General Public License for more details.
19 //
20 // Linking this library statically or dynamically with other modules is making a
21 // combined work based on this library. Thus, the terms and conditions of the GNU
22 // General Public License cover the whole combination.
23 //
24 // As a special exception, the copyright holders of this library give you
25 // permission to link this library with independent modules to produce an
26 // executable, regardless of the license terms of these independent modules, and
27 // to copy and distribute the resulting executable under terms of your choice,
28 // provided that you also meet, for each linked independent module, the terms
29 // and conditions of the license of that module. An independent module is a module
30 // which is not derived from or based on this library. If you modify this library,
31 // you may extend this exception to your version of the library, but you are not
32 // obligated to do so. If you do not wish to do so, delete this exception
33 // statement from your version.
34 //
35 // A copy of the GNU General Public License is provided in the file gpl.txt. You
36 // may also obtain a copy of the GNU General Public License on the World Wide
37 // Web at http://www.gnu.org/licenses/gpl.html.
38 //
39 //******************************************************************************
40 package edu.rit.util;
41
42 import java.util.Comparator;
43
44 /**
45 * Class Searching provides static methods for searching arrays of primitive
46 * types and object types.
47 * <P>
48 * <I>Note:</I> The operations in class Searching are not multiple thread safe.
49 *
50 * @author Alan Kaminsky
51 * @version 22-Nov-2011
52 */
53 @SuppressWarnings("unchecked")
54 public class Searching {
55
56 // Prevent construction.
57 private Searching() {
58 }
59
60 // Exported helper classes.
61 /**
62 * Class Searching.Byte is the base class for a helper object used to search
63 * an array of type <code>byte[]</code>.
64 *
65 * @author Alan Kaminsky
66 * @version 22-Nov-2011
67 */
68 public static class Byte {
69
70 /**
71 * Compare two elements according to the desired ordering criterion.
72 * <P>
73 * The default implementation compares <code>a</code> and <code>b</code> using
74 * ascending order. A subclass can override this method to obtain a
75 * different ordering criterion; for example, descending order.
76 *
77 * @param a First element being compared.
78 * @param b Second element being compared.
79 *
80 * @return A number less than, equal to, or greater than 0 if
81 * <code>a</code> comes before, is the same as, or comes after
82 * <code>b</code>, respectively.
83 */
84 public int compare(byte a,
85 byte b) {
86 return a - b;
87 }
88 }
89
90 /**
91 * Class Searching.Character is the base class for a helper object used to
92 * search an array of type <code>char[]</code>.
93 *
94 * @author Alan Kaminsky
95 * @version 22-Nov-2011
96 */
97 public static class Character {
98
99 /**
100 * Compare two elements according to the desired ordering criterion.
101 * <P>
102 * The default implementation compares <code>a</code> and <code>b</code> using
103 * ascending order. A subclass can override this method to obtain a
104 * different ordering criterion; for example, descending order.
105 *
106 * @param a First element being compared.
107 * @param b Second element being compared.
108 *
109 * @return A number less than, equal to, or greater than 0 if
110 * <code>a</code> comes before, is the same as, or comes after
111 * <code>b</code>, respectively.
112 */
113 public int compare(char a,
114 char b) {
115 return a - b;
116 }
117 }
118
119 /**
120 * Class Searching.Short is the base class for a helper object used to
121 * search an array of type <code>short[]</code>.
122 *
123 * @author Alan Kaminsky
124 * @version 22-Nov-2011
125 */
126 public static class Short {
127
128 /**
129 * Compare two elements according to the desired ordering criterion.
130 * <P>
131 * The default implementation compares <code>a</code> and <code>b</code> using
132 * ascending order. A subclass can override this method to obtain a
133 * different ordering criterion; for example, descending order.
134 *
135 * @param a First element being compared.
136 * @param b Second element being compared.
137 *
138 * @return A number less than, equal to, or greater than 0 if
139 * <code>a</code> comes before, is the same as, or comes after
140 * <code>b</code>, respectively.
141 */
142 public int compare(short a,
143 short b) {
144 return a - b;
145 }
146 }
147
148 /**
149 * Class Searching.Integer is the base class for a helper object used to
150 * search an array of type <code>int[]</code>.
151 *
152 * @author Alan Kaminsky
153 * @version 22-Nov-2011
154 */
155 public static class Integer {
156
157 /**
158 * Compare two elements according to the desired ordering criterion.
159 * <P>
160 * The default implementation compares <code>a</code> and <code>b</code> using
161 * ascending order. A subclass can override this method to obtain a
162 * different ordering criterion; for example, descending order.
163 *
164 * @param a First element being compared.
165 * @param b Second element being compared.
166 *
167 * @return A number less than, equal to, or greater than 0 if
168 * <code>a</code> comes before, is the same as, or comes after
169 * <code>b</code>, respectively.
170 */
171 public int compare(int a,
172 int b) {
173 return a - b;
174 }
175 }
176
177 /**
178 * Class Searching.Long is the base class for a helper object used to search
179 * an array of type <code>long[]</code>.
180 *
181 * @author Alan Kaminsky
182 * @version 22-Nov-2011
183 */
184 public static class Long {
185
186 /**
187 * Compare two elements according to the desired ordering criterion.
188 * <P>
189 * The default implementation compares <code>a</code> and <code>b</code> using
190 * ascending order. A subclass can override this method to obtain a
191 * different ordering criterion; for example, descending order.
192 *
193 * @param a First element being compared.
194 * @param b Second element being compared.
195 *
196 * @return A number less than, equal to, or greater than 0 if
197 * <code>a</code> comes before, is the same as, or comes after
198 * <code>b</code>, respectively.
199 */
200 public int compare(long a,
201 long b) {
202 long d = a - b;
203 return d < 0L ? -1 : d > 0L ? 1 : 0;
204 }
205 }
206
207 /**
208 * Class Searching.Float is the base class for a helper object used to
209 * search an array of type <code>float[]</code>.
210 *
211 * @author Alan Kaminsky
212 * @version 22-Nov-2011
213 */
214 public static class Float {
215
216 /**
217 * Compare two elements according to the desired ordering criterion.
218 * <P>
219 * The default implementation compares <code>a</code> and <code>b</code> using
220 * ascending order. A subclass can override this method to obtain a
221 * different ordering criterion; for example, descending order.
222 *
223 * @param a First element being compared.
224 * @param b Second element being compared.
225 *
226 * @return A number less than, equal to, or greater than 0 if
227 * <code>a</code> comes before, is the same as, or comes after
228 * <code>b</code>, respectively.
229 */
230 public int compare(float a,
231 float b) {
232 float d = a - b;
233 return d < 0.0f ? -1 : d > 0.0f ? 1 : 0;
234 }
235 }
236
237 /**
238 * Class Searching.Double is the base class for a helper object used to
239 * search an array of type <code>double[]</code>.
240 *
241 * @author Alan Kaminsky
242 * @version 22-Nov-2011
243 */
244 public static class Double {
245
246 /**
247 * Compare two elements according to the desired ordering criterion.
248 * <P>
249 * The default implementation compares <code>a</code> and <code>b</code> using
250 * ascending order. A subclass can override this method to obtain a
251 * different ordering criterion; for example, descending order.
252 *
253 * @param a First element being compared.
254 * @param b Second element being compared.
255 *
256 * @return A number less than, equal to, or greater than 0 if
257 * <code>a</code> comes before, is the same as, or comes after
258 * <code>b</code>, respectively.
259 */
260 public int compare(double a,
261 double b) {
262 double d = a - b;
263 return d < 0.0 ? -1 : d > 0.0 ? 1 : 0;
264 }
265 }
266
267 /**
268 * Class Searching.Object is the base class for a helper object used to
269 * search an array of type <code>T[]</code>.
270 *
271 * @param <T> Array element data type.
272 *
273 * @author Alan Kaminsky
274 * @version 22-Nov-2011
275 */
276 public static abstract class Object<T> {
277
278 /**
279 * Compare two elements according to the desired ordering criterion.
280 *
281 * @param a First element being compared.
282 * @param b Second element being compared.
283 *
284 * @return A number less than, equal to, or greater than 0 if
285 * <code>a</code> comes before, is the same as, or comes after
286 * <code>b</code>, respectively.
287 */
288 public abstract int compare(T a,
289 T b);
290 }
291
292 // Exported operations.
293 /**
294 * Search the given unordered array of type <code>byte[]</code> for the given
295 * element. The given helper object is used to compare elements for equality
296 * only. An <I>O</I>(<I>n</I>) linear search algorithm is used.
297 *
298 * @param x Array to be searched.
299 * @param a Element to be searched for.
300 * @param helper Helper object.
301 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
302 * the index of that element is returned. Otherwise, −1 is returned.
303 */
304 public static int searchUnsorted(byte[] x,
305 byte a,
306 Searching.Byte helper) {
307 for (int i = 0; i < x.length; ++i) {
308 if (helper.compare(x[i], a) == 0) {
309 return i;
310 }
311 }
312 return -1;
313 }
314
315 /**
316 * Search the given ordered array of type <code>byte[]</code> for the given
317 * element. The given helper object is used to compare elements for order
318 * and equality. It is assumed that the array is sorted in the order
319 * determined by the helper object; otherwise, the <code>searchSorted()</code>
320 * method's behavior is not specified. An <I>O</I>(log <I>n</I>) binary
321 * search algorithm is used.
322 *
323 * @param x Array to be searched.
324 * @param a Element to be searched for.
325 * @param helper Helper object.
326 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
327 * the index of that element is returned. Otherwise, −1 is returned.
328 */
329 public static int searchSorted(byte[] x,
330 byte a,
331 Searching.Byte helper) {
332 // Establish loop invariant.
333 if (x.length == 0) {
334 return -1;
335 }
336
337 int lo = 0;
338 int locomp = helper.compare(x[lo], a);
339 if (locomp == 0) {
340 return lo;
341 } else if (locomp > 0) {
342 return -1;
343 }
344
345 int hi = x.length - 1;
346 int hicomp = helper.compare(x[hi], a);
347 if (hicomp == 0) {
348 return hi;
349 } else if (hicomp < 0) {
350 return -1;
351 }
352
353 // Loop invariant: x[lo] comes before a; x[hi] comes after a.
354 while (hi - lo > 1) {
355 int mid = (hi + lo) / 2;
356 int midcomp = helper.compare(x[mid], a);
357 if (midcomp == 0) {
358 return mid;
359 } else if (midcomp < 0) {
360 lo = mid;
361 locomp = midcomp;
362 } else {
363 hi = mid;
364 hicomp = midcomp;
365 }
366 }
367
368 return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
369 }
370
371 /**
372 * Search the given unordered array of type <code>char[]</code> for the given
373 * element. The given helper object is used to compare elements for equality
374 * only. An <I>O</I>(<I>n</I>) linear search algorithm is used.
375 *
376 * @param x Array to be searched.
377 * @param a Element to be searched for.
378 * @param helper Helper object.
379 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
380 * the index of that element is returned. Otherwise, −1 is returned.
381 */
382 public static int searchUnsorted(char[] x,
383 char a,
384 Searching.Character helper) {
385 for (int i = 0; i < x.length; ++i) {
386 if (helper.compare(x[i], a) == 0) {
387 return i;
388 }
389 }
390 return -1;
391 }
392
393 /**
394 * Search the given ordered array of type <code>char[]</code> for the given
395 * element. The given helper object is used to compare elements for order
396 * and equality. It is assumed that the array is sorted in the order
397 * determined by the helper object; otherwise, the <code>searchSorted()</code>
398 * method's behavior is not specified. An <I>O</I>(log <I>n</I>) binary
399 * search algorithm is used.
400 *
401 * @param x Array to be searched.
402 * @param a Element to be searched for.
403 * @param helper Helper object.
404 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
405 * the index of that element is returned. Otherwise, −1 is returned.
406 */
407 public static int searchSorted(char[] x,
408 char a,
409 Searching.Character helper) {
410 // Establish loop invariant.
411 if (x.length == 0) {
412 return -1;
413 }
414
415 int lo = 0;
416 int locomp = helper.compare(x[lo], a);
417 if (locomp == 0) {
418 return lo;
419 } else if (locomp > 0) {
420 return -1;
421 }
422
423 int hi = x.length - 1;
424 int hicomp = helper.compare(x[hi], a);
425 if (hicomp == 0) {
426 return hi;
427 } else if (hicomp < 0) {
428 return -1;
429 }
430
431 // Loop invariant: x[lo] comes before a; x[hi] comes after a.
432 while (hi - lo > 1) {
433 int mid = (hi + lo) / 2;
434 int midcomp = helper.compare(x[mid], a);
435 if (midcomp == 0) {
436 return mid;
437 } else if (midcomp < 0) {
438 lo = mid;
439 locomp = midcomp;
440 } else {
441 hi = mid;
442 hicomp = midcomp;
443 }
444 }
445
446 return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
447 }
448
449 /**
450 * Search the given unordered array of type <code>short[]</code> for the given
451 * element. The given helper object is used to compare elements for equality
452 * only. An <I>O</I>(<I>n</I>) linear search algorithm is used.
453 *
454 * @param x Array to be searched.
455 * @param a Element to be searched for.
456 * @param helper Helper object.
457 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
458 * the index of that element is returned. Otherwise, −1 is returned.
459 */
460 public static int searchUnsorted(short[] x,
461 short a,
462 Searching.Short helper) {
463 for (int i = 0; i < x.length; ++i) {
464 if (helper.compare(x[i], a) == 0) {
465 return i;
466 }
467 }
468 return -1;
469 }
470
471 /**
472 * Search the given ordered array of type <code>short[]</code> for the given
473 * element. The given helper object is used to compare elements for order
474 * and equality. It is assumed that the array is sorted in the order
475 * determined by the helper object; otherwise, the <code>searchSorted()</code>
476 * method's behavior is not specified. An <I>O</I>(log <I>n</I>) binary
477 * search algorithm is used.
478 *
479 * @param x Array to be searched.
480 * @param a Element to be searched for.
481 * @param helper Helper object.
482 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
483 * the index of that element is returned. Otherwise, −1 is returned.
484 */
485 public static int searchSorted(short[] x,
486 short a,
487 Searching.Short helper) {
488 // Establish loop invariant.
489 if (x.length == 0) {
490 return -1;
491 }
492
493 int lo = 0;
494 int locomp = helper.compare(x[lo], a);
495 if (locomp == 0) {
496 return lo;
497 } else if (locomp > 0) {
498 return -1;
499 }
500
501 int hi = x.length - 1;
502 int hicomp = helper.compare(x[hi], a);
503 if (hicomp == 0) {
504 return hi;
505 } else if (hicomp < 0) {
506 return -1;
507 }
508
509 // Loop invariant: x[lo] comes before a; x[hi] comes after a.
510 while (hi - lo > 1) {
511 int mid = (hi + lo) / 2;
512 int midcomp = helper.compare(x[mid], a);
513 if (midcomp == 0) {
514 return mid;
515 } else if (midcomp < 0) {
516 lo = mid;
517 locomp = midcomp;
518 } else {
519 hi = mid;
520 hicomp = midcomp;
521 }
522 }
523
524 return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
525 }
526
527 /**
528 * Search the given unordered array of type <code>int[]</code> for the given
529 * element. The given helper object is used to compare elements for equality
530 * only. An <I>O</I>(<I>n</I>) linear search algorithm is used.
531 *
532 * @param x Array to be searched.
533 * @param a Element to be searched for.
534 * @param helper Helper object.
535 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
536 * the index of that element is returned. Otherwise, −1 is returned.
537 */
538 public static int searchUnsorted(int[] x,
539 int a,
540 Searching.Integer helper) {
541 for (int i = 0; i < x.length; ++i) {
542 if (helper.compare(x[i], a) == 0) {
543 return i;
544 }
545 }
546 return -1;
547 }
548
549 /**
550 * Search the given ordered array of type <code>int[]</code> for the given
551 * element. The given helper object is used to compare elements for order
552 * and equality. It is assumed that the array is sorted in the order
553 * determined by the helper object; otherwise, the <code>searchSorted()</code>
554 * method's behavior is not specified. An <I>O</I>(log <I>n</I>) binary
555 * search algorithm is used.
556 *
557 * @param x Array to be searched.
558 * @param a Element to be searched for.
559 * @param helper Helper object.
560 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
561 * the index of that element is returned. Otherwise, −1 is returned.
562 */
563 public static int searchSorted(int[] x,
564 int a,
565 Searching.Integer helper) {
566 // Establish loop invariant.
567 if (x.length == 0) {
568 return -1;
569 }
570
571 int lo = 0;
572 int locomp = helper.compare(x[lo], a);
573 if (locomp == 0) {
574 return lo;
575 } else if (locomp > 0) {
576 return -1;
577 }
578
579 int hi = x.length - 1;
580 int hicomp = helper.compare(x[hi], a);
581 if (hicomp == 0) {
582 return hi;
583 } else if (hicomp < 0) {
584 return -1;
585 }
586
587 // Loop invariant: x[lo] comes before a; x[hi] comes after a.
588 while (hi - lo > 1) {
589 int mid = (hi + lo) / 2;
590 int midcomp = helper.compare(x[mid], a);
591 if (midcomp == 0) {
592 return mid;
593 } else if (midcomp < 0) {
594 lo = mid;
595 locomp = midcomp;
596 } else {
597 hi = mid;
598 hicomp = midcomp;
599 }
600 }
601
602 return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
603 }
604
605 /**
606 * Search the given unordered array of type <code>long[]</code> for the given
607 * element. The given helper object is used to compare elements for equality
608 * only. An <I>O</I>(<I>n</I>) linear search algorithm is used.
609 *
610 * @param x Array to be searched.
611 * @param a Element to be searched for.
612 * @param helper Helper object.
613 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
614 * the index of that element is returned. Otherwise, −1 is returned.
615 */
616 public static int searchUnsorted(long[] x,
617 long a,
618 Searching.Long helper) {
619 for (int i = 0; i < x.length; ++i) {
620 if (helper.compare(x[i], a) == 0) {
621 return i;
622 }
623 }
624 return -1;
625 }
626
627 /**
628 * Search the given ordered array of type <code>long[]</code> for the given
629 * element. The given helper object is used to compare elements for order
630 * and equality. It is assumed that the array is sorted in the order
631 * determined by the helper object; otherwise, the <code>searchSorted()</code>
632 * method's behavior is not specified. An <I>O</I>(log <I>n</I>) binary
633 * search algorithm is used.
634 *
635 * @param x Array to be searched.
636 * @param a Element to be searched for.
637 * @param helper Helper object.
638 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
639 * the index of that element is returned. Otherwise, −1 is returned.
640 */
641 public static int searchSorted(long[] x,
642 long a,
643 Searching.Long helper) {
644 // Establish loop invariant.
645 if (x.length == 0) {
646 return -1;
647 }
648
649 int lo = 0;
650 int locomp = helper.compare(x[lo], a);
651 if (locomp == 0) {
652 return lo;
653 } else if (locomp > 0) {
654 return -1;
655 }
656
657 int hi = x.length - 1;
658 int hicomp = helper.compare(x[hi], a);
659 if (hicomp == 0) {
660 return hi;
661 } else if (hicomp < 0) {
662 return -1;
663 }
664
665 // Loop invariant: x[lo] comes before a; x[hi] comes after a.
666 while (hi - lo > 1) {
667 int mid = (hi + lo) / 2;
668 int midcomp = helper.compare(x[mid], a);
669 if (midcomp == 0) {
670 return mid;
671 } else if (midcomp < 0) {
672 lo = mid;
673 locomp = midcomp;
674 } else {
675 hi = mid;
676 hicomp = midcomp;
677 }
678 }
679
680 return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
681 }
682
683 /**
684 * Search the given unordered array of type <code>float[]</code> for the given
685 * element. The given helper object is used to compare elements for equality
686 * only. An <I>O</I>(<I>n</I>) linear search algorithm is used.
687 *
688 * @param x Array to be searched.
689 * @param a Element to be searched for.
690 * @param helper Helper object.
691 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
692 * the index of that element is returned. Otherwise, −1 is returned.
693 */
694 public static int searchUnsorted(float[] x,
695 float a,
696 Searching.Float helper) {
697 for (int i = 0; i < x.length; ++i) {
698 if (helper.compare(x[i], a) == 0) {
699 return i;
700 }
701 }
702 return -1;
703 }
704
705 /**
706 * Search the given ordered array of type <code>float[]</code> for the given
707 * element. The given helper object is used to compare elements for order
708 * and equality. It is assumed that the array is sorted in the order
709 * determined by the helper object; otherwise, the <code>searchSorted()</code>
710 * method's behavior is not specified. An <I>O</I>(log <I>n</I>) binary
711 * search algorithm is used.
712 *
713 * @param x Array to be searched.
714 * @param a Element to be searched for.
715 * @param helper Helper object.
716 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
717 * the index of that element is returned. Otherwise, −1 is returned.
718 */
719 public static int searchSorted(float[] x,
720 float a,
721 Searching.Float helper) {
722 // Establish loop invariant.
723 if (x.length == 0) {
724 return -1;
725 }
726
727 int lo = 0;
728 int locomp = helper.compare(x[lo], a);
729 if (locomp == 0) {
730 return lo;
731 } else if (locomp > 0) {
732 return -1;
733 }
734
735 int hi = x.length - 1;
736 int hicomp = helper.compare(x[hi], a);
737 if (hicomp == 0) {
738 return hi;
739 } else if (hicomp < 0) {
740 return -1;
741 }
742
743 // Loop invariant: x[lo] comes before a; x[hi] comes after a.
744 while (hi - lo > 1) {
745 int mid = (hi + lo) / 2;
746 int midcomp = helper.compare(x[mid], a);
747 if (midcomp == 0) {
748 return mid;
749 } else if (midcomp < 0) {
750 lo = mid;
751 locomp = midcomp;
752 } else {
753 hi = mid;
754 hicomp = midcomp;
755 }
756 }
757
758 return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
759 }
760
761 /**
762 * Search the given unordered array of type <code>double[]</code> for the given
763 * element. The given helper object is used to compare elements for equality
764 * only. An <I>O</I>(<I>n</I>) linear search algorithm is used.
765 *
766 * @param x Array to be searched.
767 * @param a Element to be searched for.
768 * @param helper Helper object.
769 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
770 * the index of that element is returned. Otherwise, −1 is returned.
771 */
772 public static int searchUnsorted(double[] x,
773 double a,
774 Searching.Double helper) {
775 for (int i = 0; i < x.length; ++i) {
776 if (helper.compare(x[i], a) == 0) {
777 return i;
778 }
779 }
780 return -1;
781 }
782
783 /**
784 * Search the given ordered array of type <code>double[]</code> for the given
785 * element. The given helper object is used to compare elements for order
786 * and equality. It is assumed that the array is sorted in the order
787 * determined by the helper object; otherwise, the <code>searchSorted()</code>
788 * method's behavior is not specified. An <I>O</I>(log <I>n</I>) binary
789 * search algorithm is used.
790 *
791 * @param x Array to be searched.
792 * @param a Element to be searched for.
793 * @param helper Helper object.
794 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
795 * the index of that element is returned. Otherwise, −1 is returned.
796 */
797 public static int searchSorted(double[] x,
798 double a,
799 Searching.Double helper) {
800 // Establish loop invariant.
801 if (x.length == 0) {
802 return -1;
803 }
804
805 int lo = 0;
806 int locomp = helper.compare(x[lo], a);
807 if (locomp == 0) {
808 return lo;
809 } else if (locomp > 0) {
810 return -1;
811 }
812
813 int hi = x.length - 1;
814 int hicomp = helper.compare(x[hi], a);
815 if (hicomp == 0) {
816 return hi;
817 } else if (hicomp < 0) {
818 return -1;
819 }
820
821 // Loop invariant: x[lo] comes before a; x[hi] comes after a.
822 while (hi - lo > 1) {
823 int mid = (hi + lo) / 2;
824 int midcomp = helper.compare(x[mid], a);
825 if (midcomp == 0) {
826 return mid;
827 } else if (midcomp < 0) {
828 lo = mid;
829 locomp = midcomp;
830 } else {
831 hi = mid;
832 hicomp = midcomp;
833 }
834 }
835
836 return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
837 }
838
839 /**
840 * Search the given unordered array of type <code>T[]</code> for the given
841 * element. The given helper object is used to compare elements for equality
842 * only. An <I>O</I>(<I>n</I>) linear search algorithm is used.
843 *
844 * @param <T> Array element data type.
845 * @param x Array to be searched.
846 * @param a Element to be searched for.
847 * @param helper Helper object.
848 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
849 * the index of that element is returned. Otherwise, −1 is returned.
850 */
851 public static <T> int searchUnsorted(T[] x,
852 T a,
853 Searching.Object<T> helper) {
854 for (int i = 0; i < x.length; ++i) {
855 if (helper.compare(x[i], a) == 0) {
856 return i;
857 }
858 }
859 return -1;
860 }
861
862 /**
863 * Search the given ordered array of type <code>T[]</code> for the given
864 * element. The given helper object is used to compare elements for order
865 * and equality. It is assumed that the array is sorted in the order
866 * determined by the helper object; otherwise, the <code>searchSorted()</code>
867 * method's behavior is not specified. An <I>O</I>(log <I>n</I>) binary
868 * search algorithm is used.
869 *
870 * @param <T> Array element data type.
871 * @param x Array to be searched.
872 * @param a Element to be searched for.
873 * @param helper Helper object.
874 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
875 * the index of that element is returned. Otherwise, −1 is returned.
876 */
877 public static <T> int searchSorted(T[] x,
878 T a,
879 Searching.Object<T> helper) {
880 // Establish loop invariant.
881 if (x.length == 0) {
882 return -1;
883 }
884
885 int lo = 0;
886 int locomp = helper.compare(x[lo], a);
887 if (locomp == 0) {
888 return lo;
889 } else if (locomp > 0) {
890 return -1;
891 }
892
893 int hi = x.length - 1;
894 int hicomp = helper.compare(x[hi], a);
895 if (hicomp == 0) {
896 return hi;
897 } else if (hicomp < 0) {
898 return -1;
899 }
900
901 // Loop invariant: x[lo] comes before a; x[hi] comes after a.
902 while (hi - lo > 1) {
903 int mid = (hi + lo) / 2;
904 int midcomp = helper.compare(x[mid], a);
905 if (midcomp == 0) {
906 return mid;
907 } else if (midcomp < 0) {
908 lo = mid;
909 locomp = midcomp;
910 } else {
911 hi = mid;
912 hicomp = midcomp;
913 }
914 }
915
916 return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
917 }
918
919 /**
920 * Search the given unordered array of type <code>T[]</code> for the given
921 * element. The given comparator is used to compare elements for equality
922 * only. An <I>O</I>(<I>n</I>) linear search algorithm is used.
923 *
924 * @param <T> Array element data type.
925 * @param x Array to be searched.
926 * @param a Element to be searched for.
927 * @param comp Comparator.
928 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
929 * the index of that element is returned. Otherwise, −1 is returned.
930 */
931 public static <T> int searchUnsorted(T[] x,
932 T a,
933 Comparator<T> comp) {
934 for (int i = 0; i < x.length; ++i) {
935 if (comp.compare(x[i], a) == 0) {
936 return i;
937 }
938 }
939 return -1;
940 }
941
942 /**
943 * Search the given ordered array of type <code>T[]</code> for the given
944 * element. The given comparator is used to compare elements for order and
945 * equality. It is assumed that the array is sorted in the order determined
946 * by the comparator; otherwise, the <code>searchSorted()</code> method's
947 * behavior is not specified. An <I>O</I>(log <I>n</I>) binary search
948 * algorithm is used.
949 *
950 * @param <T> Array element data type.
951 * @param x Array to be searched.
952 * @param a Element to be searched for.
953 * @param comp Comparator.
954 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
955 * the index of that element is returned. Otherwise, −1 is returned.
956 */
957 public static <T> int searchSorted(T[] x,
958 T a,
959 Comparator<T> comp) {
960 // Establish loop invariant.
961 if (x.length == 0) {
962 return -1;
963 }
964
965 int lo = 0;
966 int locomp = comp.compare(x[lo], a);
967 if (locomp == 0) {
968 return lo;
969 } else if (locomp > 0) {
970 return -1;
971 }
972
973 int hi = x.length - 1;
974 int hicomp = comp.compare(x[hi], a);
975 if (hicomp == 0) {
976 return hi;
977 } else if (hicomp < 0) {
978 return -1;
979 }
980
981 // Loop invariant: x[lo] comes before a; x[hi] comes after a.
982 while (hi - lo > 1) {
983 int mid = (hi + lo) / 2;
984 int midcomp = comp.compare(x[mid], a);
985 if (midcomp == 0) {
986 return mid;
987 } else if (midcomp < 0) {
988 lo = mid;
989 locomp = midcomp;
990 } else {
991 hi = mid;
992 hicomp = midcomp;
993 }
994 }
995
996 return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
997 }
998
999 /**
1000 * Search the given unordered array of type <code>T[]</code> for the given
1001 * element. The array element's natural ordering (<code>compareTo()</code>
1002 * method) is used to compare elements for equality only. An
1003 * <I>O</I>(<I>n</I>) linear search algorithm is used.
1004 *
1005 * @param <T> Class that extends Comparable.
1006 * @param x Array to be searched.
1007 * @param a Element to be searched for.
1008 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
1009 * the index of that element is returned. Otherwise, −1 is returned.
1010 */
1011 public static <T extends Comparable<T>> int searchUnsorted(T[] x,
1012 T a) {
1013 for (int i = 0; i < x.length; ++i) {
1014 if (x[i].compareTo(a) == 0) {
1015 return i;
1016 }
1017 }
1018 return -1;
1019 }
1020
1021 /**
1022 * Search the given ordered array of type <code>T[]</code> for the given
1023 * element. The array element's natural ordering (<code>compareTo()</code>
1024 * method) is used to compare elements for order and equality. It is assumed
1025 * that the array is sorted in the order determined by the natural ordering;
1026 * otherwise, the <code>searchSorted()</code> method's behavior is not
1027 * specified. An <I>O</I>(log <I>n</I>) binary search algorithm is used.
1028 *
1029 * @param <T> Class that extends Comparable.
1030 * @param x Array to be searched.
1031 * @param a Element to be searched for.
1032 * @return If an element the same as <code>a</code> exists in <code>x</code>, then
1033 * the index of that element is returned. Otherwise, −1 is returned.
1034 */
1035 public static <T extends Comparable<T>> int searchSorted(T[] x, T a) {
1036 // Establish loop invariant.
1037 if (x.length == 0) {
1038 return -1;
1039 }
1040
1041 int lo = 0;
1042 int locomp = x[lo].compareTo(a);
1043 if (locomp == 0) {
1044 return lo;
1045 } else if (locomp > 0) {
1046 return -1;
1047 }
1048
1049 int hi = x.length - 1;
1050 int hicomp = x[hi].compareTo(a);
1051 if (hicomp == 0) {
1052 return hi;
1053 } else if (hicomp < 0) {
1054 return -1;
1055 }
1056
1057 // Loop invariant: x[lo] comes before a; x[hi] comes after a.
1058 while (hi - lo > 1) {
1059 int mid = (hi + lo) / 2;
1060 int midcomp = x[mid].compareTo(a);
1061 if (midcomp == 0) {
1062 return mid;
1063 } else if (midcomp < 0) {
1064 lo = mid;
1065 locomp = midcomp;
1066 } else {
1067 hi = mid;
1068 hicomp = midcomp;
1069 }
1070 }
1071
1072 return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
1073 }
1074
1075 // Unit test main program.
1076 // /**
1077 // * Unit test main program.
1078 // * <P>
1079 // * Usage: java edu.rit.util.Searching <I>a</I> <I>x_elements</I>
1080 // * <BR><I>a</I> = Element to be searched for
1081 // * <BR><I>x_elements</I> = Array elements to be searched
1082 // */
1083 // public static void main
1084 // (String[] args)
1085 // {
1086 // if (args.length < 1) usage();
1087 // int a = java.lang.Integer.parseInt (args[0]);
1088 // int n = args.length - 1;
1089 // int[] x = new int [n];
1090 // for (int i = 0; i < n; ++ i)
1091 // x[i] = java.lang.Integer.parseInt (args[i+1]);
1092 // Searching.Integer helper = new Searching.Integer();
1093 // System.out.printf ("searchUnsorted() returns %d%n",
1094 // Searching.searchUnsorted (x, a, helper));
1095 // System.out.printf ("searchSorted() returns %d%n",
1096 // Searching.searchSorted (x, a, helper));
1097 // }
1098 //
1099 // /**
1100 // * Print a usage message and exit.
1101 // */
1102 // private static void usage()
1103 // {
1104 // System.err.println ("Usage: java edu.rit.util.Searching <a> <x_elements>");
1105 // System.err.println ("<a> = Element to be searched for");
1106 // System.err.println ("<x_elements> = Array elements to be searched");
1107 // System.exit (1);
1108 // }
1109 }