//******************************************************************************
//
// File: Searching.java
// Package: edu.rit.util
// Unit: Class edu.rit.util.Searching
//
// This Java source file is copyright (C) 2011 by Alan Kaminsky. All rights
// reserved. For further information, contact the author, Alan Kaminsky, at
// ark@cs.rit.edu.
//
// This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
// software; you can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation; either
// version 3 of the License, or (at your option) any later version.
//
// PJ is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
// A PARTICULAR PURPOSE. See the GNU General Public License for more details.
//
// Linking this library statically or dynamically with other modules is making a
// combined work based on this library. Thus, the terms and conditions of the
// GNU General Public License cover the whole combination.
//
// As a special exception, the copyright holders of this library give you
// permission to link this library with independent modules to produce an
// executable, regardless of the license terms of these independent modules, and
// to copy and distribute the resulting executable under terms of your choice,
// provided that you also meet, for each linked independent module, the terms
// and conditions of the license of that module. An independent module is a
// module which is not derived from or based on this library. If you modify this
// library, you may extend this exception to your version of the library, but
// you are not obligated to do so. If you do not wish to do so, delete this
// exception statement from your version.
//
// A copy of the GNU General Public License is provided in the file gpl.txt. You
// may also obtain a copy of the GNU General Public License on the World Wide
// Web at http://www.gnu.org/licenses/gpl.html.
//
//******************************************************************************
package edu.rit.util;
import java.util.Comparator;
/**
* Class Searching provides static methods for searching arrays of primitive
* types and object types.
*
* Note: The operations in class Searching are not multiple thread safe.
*
* @author Alan Kaminsky
* @version 22-Nov-2011
*/
public class Searching
{
// Prevent construction.
private Searching()
{
}
// Exported helper classes.
/**
* Class Searching.Byte is the base class for a helper object used to
* search an array of type byte[].
*
* @author Alan Kaminsky
* @version 22-Nov-2011
*/
public static class Byte
{
/**
* Compare two elements according to the desired ordering criterion.
*
* The default implementation compares a and b using
* ascending order. A subclass can override this method to obtain a
* different ordering criterion; for example, descending order.
*
* @param a First element being compared.
* @param b Second element being compared.
*
* @return A number less than, equal to, or greater than 0 if
* a comes before, is the same as, or comes after
* b, respectively.
*/
public int compare
(byte a,
byte b)
{
return a - b;
}
}
/**
* Class Searching.Character is the base class for a helper object used to
* search an array of type char[].
*
* @author Alan Kaminsky
* @version 22-Nov-2011
*/
public static class Character
{
/**
* Compare two elements according to the desired ordering criterion.
*
* The default implementation compares a and b using
* ascending order. A subclass can override this method to obtain a
* different ordering criterion; for example, descending order.
*
* @param a First element being compared.
* @param b Second element being compared.
*
* @return A number less than, equal to, or greater than 0 if
* a comes before, is the same as, or comes after
* b, respectively.
*/
public int compare
(char a,
char b)
{
return a - b;
}
}
/**
* Class Searching.Short is the base class for a helper object used to
* search an array of type short[].
*
* @author Alan Kaminsky
* @version 22-Nov-2011
*/
public static class Short
{
/**
* Compare two elements according to the desired ordering criterion.
*
* The default implementation compares a and b using
* ascending order. A subclass can override this method to obtain a
* different ordering criterion; for example, descending order.
*
* @param a First element being compared.
* @param b Second element being compared.
*
* @return A number less than, equal to, or greater than 0 if
* a comes before, is the same as, or comes after
* b, respectively.
*/
public int compare
(short a,
short b)
{
return a - b;
}
}
/**
* Class Searching.Integer is the base class for a helper object used to
* search an array of type int[].
*
* @author Alan Kaminsky
* @version 22-Nov-2011
*/
public static class Integer
{
/**
* Compare two elements according to the desired ordering criterion.
*
* The default implementation compares a and b using
* ascending order. A subclass can override this method to obtain a
* different ordering criterion; for example, descending order.
*
* @param a First element being compared.
* @param b Second element being compared.
*
* @return A number less than, equal to, or greater than 0 if
* a comes before, is the same as, or comes after
* b, respectively.
*/
public int compare
(int a,
int b)
{
return a - b;
}
}
/**
* Class Searching.Long is the base class for a helper object used to
* search an array of type long[].
*
* @author Alan Kaminsky
* @version 22-Nov-2011
*/
public static class Long
{
/**
* Compare two elements according to the desired ordering criterion.
*
* The default implementation compares a and b using
* ascending order. A subclass can override this method to obtain a
* different ordering criterion; for example, descending order.
*
* @param a First element being compared.
* @param b Second element being compared.
*
* @return A number less than, equal to, or greater than 0 if
* a comes before, is the same as, or comes after
* b, respectively.
*/
public int compare
(long a,
long b)
{
long d = a - b;
return d < 0L ? -1 : d > 0L ? 1 : 0;
}
}
/**
* Class Searching.Float is the base class for a helper object used to
* search an array of type float[].
*
* @author Alan Kaminsky
* @version 22-Nov-2011
*/
public static class Float
{
/**
* Compare two elements according to the desired ordering criterion.
*
* The default implementation compares a and b using
* ascending order. A subclass can override this method to obtain a
* different ordering criterion; for example, descending order.
*
* @param a First element being compared.
* @param b Second element being compared.
*
* @return A number less than, equal to, or greater than 0 if
* a comes before, is the same as, or comes after
* b, respectively.
*/
public int compare
(float a,
float b)
{
float d = a - b;
return d < 0.0f ? -1 : d > 0.0f ? 1 : 0;
}
}
/**
* Class Searching.Double is the base class for a helper object used to
* search an array of type double[].
*
* @author Alan Kaminsky
* @version 22-Nov-2011
*/
public static class Double
{
/**
* Compare two elements according to the desired ordering criterion.
*
* The default implementation compares a and b using
* ascending order. A subclass can override this method to obtain a
* different ordering criterion; for example, descending order.
*
* @param a First element being compared.
* @param b Second element being compared.
*
* @return A number less than, equal to, or greater than 0 if
* a comes before, is the same as, or comes after
* b, respectively.
*/
public int compare
(double a,
double b)
{
double d = a - b;
return d < 0.0 ? -1 : d > 0.0 ? 1 : 0;
}
}
/**
* Class Searching.Object is the base class for a helper object used to
* search an array of type T[].
*
* @param Array element data type.
*
* @author Alan Kaminsky
* @version 22-Nov-2011
*/
public static abstract class Object
{
/**
* Compare two elements according to the desired ordering criterion.
*
* @param a First element being compared.
* @param b Second element being compared.
*
* @return A number less than, equal to, or greater than 0 if
* a comes before, is the same as, or comes after
* b, respectively.
*/
public abstract int compare
(T a,
T b);
}
// Exported operations.
/**
* Search the given unordered array of type byte[] for the given
* element. The given helper object is used to compare elements for
* equality only. An O(n) linear search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchUnsorted
(byte[] x,
byte a,
Searching.Byte helper)
{
for (int i = 0; i < x.length; ++ i)
{
if (helper.compare (x[i], a) == 0) return i;
}
return -1;
}
/**
* Search the given ordered array of type byte[] for the given
* element. The given helper object is used to compare elements for order
* and equality. It is assumed that the array is sorted in the order
* determined by the helper object; otherwise, the searchSorted()
* method's behavior is not specified. An O(log n) binary
* search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchSorted
(byte[] x,
byte a,
Searching.Byte helper)
{
// Establish loop invariant.
if (x.length == 0) return -1;
int lo = 0;
int locomp = helper.compare (x[lo], a);
if (locomp == 0) return lo;
else if (locomp > 0) return -1;
int hi = x.length - 1;
int hicomp = helper.compare (x[hi], a);
if (hicomp == 0) return hi;
else if (hicomp < 0) return -1;
// Loop invariant: x[lo] comes before a; x[hi] comes after a.
while (hi - lo > 1)
{
int mid = (hi + lo)/2;
int midcomp = helper.compare (x[mid], a);
if (midcomp == 0)
{
return mid;
}
else if (midcomp < 0)
{
lo = mid;
locomp = midcomp;
}
else
{
hi = mid;
hicomp = midcomp;
}
}
return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
}
/**
* Search the given unordered array of type char[] for the given
* element. The given helper object is used to compare elements for
* equality only. An O(n) linear search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchUnsorted
(char[] x,
char a,
Searching.Character helper)
{
for (int i = 0; i < x.length; ++ i)
{
if (helper.compare (x[i], a) == 0) return i;
}
return -1;
}
/**
* Search the given ordered array of type char[] for the given
* element. The given helper object is used to compare elements for order
* and equality. It is assumed that the array is sorted in the order
* determined by the helper object; otherwise, the searchSorted()
* method's behavior is not specified. An O(log n) binary
* search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchSorted
(char[] x,
char a,
Searching.Character helper)
{
// Establish loop invariant.
if (x.length == 0) return -1;
int lo = 0;
int locomp = helper.compare (x[lo], a);
if (locomp == 0) return lo;
else if (locomp > 0) return -1;
int hi = x.length - 1;
int hicomp = helper.compare (x[hi], a);
if (hicomp == 0) return hi;
else if (hicomp < 0) return -1;
// Loop invariant: x[lo] comes before a; x[hi] comes after a.
while (hi - lo > 1)
{
int mid = (hi + lo)/2;
int midcomp = helper.compare (x[mid], a);
if (midcomp == 0)
{
return mid;
}
else if (midcomp < 0)
{
lo = mid;
locomp = midcomp;
}
else
{
hi = mid;
hicomp = midcomp;
}
}
return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
}
/**
* Search the given unordered array of type short[] for the given
* element. The given helper object is used to compare elements for
* equality only. An O(n) linear search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchUnsorted
(short[] x,
short a,
Searching.Short helper)
{
for (int i = 0; i < x.length; ++ i)
{
if (helper.compare (x[i], a) == 0) return i;
}
return -1;
}
/**
* Search the given ordered array of type short[] for the given
* element. The given helper object is used to compare elements for order
* and equality. It is assumed that the array is sorted in the order
* determined by the helper object; otherwise, the searchSorted()
* method's behavior is not specified. An O(log n) binary
* search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchSorted
(short[] x,
short a,
Searching.Short helper)
{
// Establish loop invariant.
if (x.length == 0) return -1;
int lo = 0;
int locomp = helper.compare (x[lo], a);
if (locomp == 0) return lo;
else if (locomp > 0) return -1;
int hi = x.length - 1;
int hicomp = helper.compare (x[hi], a);
if (hicomp == 0) return hi;
else if (hicomp < 0) return -1;
// Loop invariant: x[lo] comes before a; x[hi] comes after a.
while (hi - lo > 1)
{
int mid = (hi + lo)/2;
int midcomp = helper.compare (x[mid], a);
if (midcomp == 0)
{
return mid;
}
else if (midcomp < 0)
{
lo = mid;
locomp = midcomp;
}
else
{
hi = mid;
hicomp = midcomp;
}
}
return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
}
/**
* Search the given unordered array of type int[] for the given
* element. The given helper object is used to compare elements for
* equality only. An O(n) linear search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchUnsorted
(int[] x,
int a,
Searching.Integer helper)
{
for (int i = 0; i < x.length; ++ i)
{
if (helper.compare (x[i], a) == 0) return i;
}
return -1;
}
/**
* Search the given ordered array of type int[] for the given
* element. The given helper object is used to compare elements for order
* and equality. It is assumed that the array is sorted in the order
* determined by the helper object; otherwise, the searchSorted()
* method's behavior is not specified. An O(log n) binary
* search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchSorted
(int[] x,
int a,
Searching.Integer helper)
{
// Establish loop invariant.
if (x.length == 0) return -1;
int lo = 0;
int locomp = helper.compare (x[lo], a);
if (locomp == 0) return lo;
else if (locomp > 0) return -1;
int hi = x.length - 1;
int hicomp = helper.compare (x[hi], a);
if (hicomp == 0) return hi;
else if (hicomp < 0) return -1;
// Loop invariant: x[lo] comes before a; x[hi] comes after a.
while (hi - lo > 1)
{
int mid = (hi + lo)/2;
int midcomp = helper.compare (x[mid], a);
if (midcomp == 0)
{
return mid;
}
else if (midcomp < 0)
{
lo = mid;
locomp = midcomp;
}
else
{
hi = mid;
hicomp = midcomp;
}
}
return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
}
/**
* Search the given unordered array of type long[] for the given
* element. The given helper object is used to compare elements for
* equality only. An O(n) linear search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchUnsorted
(long[] x,
long a,
Searching.Long helper)
{
for (int i = 0; i < x.length; ++ i)
{
if (helper.compare (x[i], a) == 0) return i;
}
return -1;
}
/**
* Search the given ordered array of type long[] for the given
* element. The given helper object is used to compare elements for order
* and equality. It is assumed that the array is sorted in the order
* determined by the helper object; otherwise, the searchSorted()
* method's behavior is not specified. An O(log n) binary
* search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchSorted
(long[] x,
long a,
Searching.Long helper)
{
// Establish loop invariant.
if (x.length == 0) return -1;
int lo = 0;
int locomp = helper.compare (x[lo], a);
if (locomp == 0) return lo;
else if (locomp > 0) return -1;
int hi = x.length - 1;
int hicomp = helper.compare (x[hi], a);
if (hicomp == 0) return hi;
else if (hicomp < 0) return -1;
// Loop invariant: x[lo] comes before a; x[hi] comes after a.
while (hi - lo > 1)
{
int mid = (hi + lo)/2;
int midcomp = helper.compare (x[mid], a);
if (midcomp == 0)
{
return mid;
}
else if (midcomp < 0)
{
lo = mid;
locomp = midcomp;
}
else
{
hi = mid;
hicomp = midcomp;
}
}
return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
}
/**
* Search the given unordered array of type float[] for the given
* element. The given helper object is used to compare elements for
* equality only. An O(n) linear search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchUnsorted
(float[] x,
float a,
Searching.Float helper)
{
for (int i = 0; i < x.length; ++ i)
{
if (helper.compare (x[i], a) == 0) return i;
}
return -1;
}
/**
* Search the given ordered array of type float[] for the given
* element. The given helper object is used to compare elements for order
* and equality. It is assumed that the array is sorted in the order
* determined by the helper object; otherwise, the searchSorted()
* method's behavior is not specified. An O(log n) binary
* search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchSorted
(float[] x,
float a,
Searching.Float helper)
{
// Establish loop invariant.
if (x.length == 0) return -1;
int lo = 0;
int locomp = helper.compare (x[lo], a);
if (locomp == 0) return lo;
else if (locomp > 0) return -1;
int hi = x.length - 1;
int hicomp = helper.compare (x[hi], a);
if (hicomp == 0) return hi;
else if (hicomp < 0) return -1;
// Loop invariant: x[lo] comes before a; x[hi] comes after a.
while (hi - lo > 1)
{
int mid = (hi + lo)/2;
int midcomp = helper.compare (x[mid], a);
if (midcomp == 0)
{
return mid;
}
else if (midcomp < 0)
{
lo = mid;
locomp = midcomp;
}
else
{
hi = mid;
hicomp = midcomp;
}
}
return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
}
/**
* Search the given unordered array of type double[] for the given
* element. The given helper object is used to compare elements for
* equality only. An O(n) linear search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchUnsorted
(double[] x,
double a,
Searching.Double helper)
{
for (int i = 0; i < x.length; ++ i)
{
if (helper.compare (x[i], a) == 0) return i;
}
return -1;
}
/**
* Search the given ordered array of type double[] for the given
* element. The given helper object is used to compare elements for order
* and equality. It is assumed that the array is sorted in the order
* determined by the helper object; otherwise, the searchSorted()
* method's behavior is not specified. An O(log n) binary
* search algorithm is used.
*
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchSorted
(double[] x,
double a,
Searching.Double helper)
{
// Establish loop invariant.
if (x.length == 0) return -1;
int lo = 0;
int locomp = helper.compare (x[lo], a);
if (locomp == 0) return lo;
else if (locomp > 0) return -1;
int hi = x.length - 1;
int hicomp = helper.compare (x[hi], a);
if (hicomp == 0) return hi;
else if (hicomp < 0) return -1;
// Loop invariant: x[lo] comes before a; x[hi] comes after a.
while (hi - lo > 1)
{
int mid = (hi + lo)/2;
int midcomp = helper.compare (x[mid], a);
if (midcomp == 0)
{
return mid;
}
else if (midcomp < 0)
{
lo = mid;
locomp = midcomp;
}
else
{
hi = mid;
hicomp = midcomp;
}
}
return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
}
/**
* Search the given unordered array of type T[] for the given
* element. The given helper object is used to compare elements for
* equality only. An O(n) linear search algorithm is used.
*
* @param Array element data type.
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchUnsorted
(T[] x,
T a,
Searching.Object helper)
{
for (int i = 0; i < x.length; ++ i)
{
if (helper.compare (x[i], a) == 0) return i;
}
return -1;
}
/**
* Search the given ordered array of type T[] for the given
* element. The given helper object is used to compare elements for order
* and equality. It is assumed that the array is sorted in the order
* determined by the helper object; otherwise, the searchSorted()
* method's behavior is not specified. An O(log n) binary
* search algorithm is used.
*
* @param Array element data type.
* @param x Array to be searched.
* @param a Element to be searched for.
* @param helper Helper object.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchSorted
(T[] x,
T a,
Searching.Object helper)
{
// Establish loop invariant.
if (x.length == 0) return -1;
int lo = 0;
int locomp = helper.compare (x[lo], a);
if (locomp == 0) return lo;
else if (locomp > 0) return -1;
int hi = x.length - 1;
int hicomp = helper.compare (x[hi], a);
if (hicomp == 0) return hi;
else if (hicomp < 0) return -1;
// Loop invariant: x[lo] comes before a; x[hi] comes after a.
while (hi - lo > 1)
{
int mid = (hi + lo)/2;
int midcomp = helper.compare (x[mid], a);
if (midcomp == 0)
{
return mid;
}
else if (midcomp < 0)
{
lo = mid;
locomp = midcomp;
}
else
{
hi = mid;
hicomp = midcomp;
}
}
return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
}
/**
* Search the given unordered array of type T[] for the given
* element. The given comparator is used to compare elements for equality
* only. An O(n) linear search algorithm is used.
*
* @param Array element data type.
* @param x Array to be searched.
* @param a Element to be searched for.
* @param comp Comparator.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchUnsorted
(T[] x,
T a,
Comparator comp)
{
for (int i = 0; i < x.length; ++ i)
{
if (comp.compare (x[i], a) == 0) return i;
}
return -1;
}
/**
* Search the given ordered array of type T[] for the given
* element. The given comparator is used to compare elements for order and
* equality. It is assumed that the array is sorted in the order determined
* by the comparator; otherwise, the searchSorted() method's
* behavior is not specified. An O(log n) binary search
* algorithm is used.
*
* @param Array element data type.
* @param x Array to be searched.
* @param a Element to be searched for.
* @param comp Comparator.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchSorted
(T[] x,
T a,
Comparator comp)
{
// Establish loop invariant.
if (x.length == 0) return -1;
int lo = 0;
int locomp = comp.compare (x[lo], a);
if (locomp == 0) return lo;
else if (locomp > 0) return -1;
int hi = x.length - 1;
int hicomp = comp.compare (x[hi], a);
if (hicomp == 0) return hi;
else if (hicomp < 0) return -1;
// Loop invariant: x[lo] comes before a; x[hi] comes after a.
while (hi - lo > 1)
{
int mid = (hi + lo)/2;
int midcomp = comp.compare (x[mid], a);
if (midcomp == 0)
{
return mid;
}
else if (midcomp < 0)
{
lo = mid;
locomp = midcomp;
}
else
{
hi = mid;
hicomp = midcomp;
}
}
return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
}
/**
* Search the given unordered array of type T[] for the given
* element. The array element's natural ordering (compareTo()
* method) is used to compare elements for equality only. An
* O(n) linear search algorithm is used.
*
* @param Array element data type.
* @param x Array to be searched.
* @param a Element to be searched for.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchUnsorted
(T[] x,
T a)
{
for (int i = 0; i < x.length; ++ i)
{
if (x[i].compareTo (a) == 0) return i;
}
return -1;
}
/**
* Search the given ordered array of type T[] for the given
* element. The array element's natural ordering (compareTo()
* method) is used to compare elements for order and equality. It is assumed
* that the array is sorted in the order determined by the natural ordering;
* otherwise, the searchSorted() method's behavior is not
* specified. An O(log n) binary search algorithm is used.
*
* @param Array element data type.
* @param x Array to be searched.
* @param a Element to be searched for.
*
* @return If an element the same as a exists in x, then
* the index of that element is returned. Otherwise, −1 is
* returned.
*/
public static int searchSorted
(T[] x,
T a)
{
// Establish loop invariant.
if (x.length == 0) return -1;
int lo = 0;
int locomp = x[lo].compareTo (a);
if (locomp == 0) return lo;
else if (locomp > 0) return -1;
int hi = x.length - 1;
int hicomp = x[hi].compareTo (a);
if (hicomp == 0) return hi;
else if (hicomp < 0) return -1;
// Loop invariant: x[lo] comes before a; x[hi] comes after a.
while (hi - lo > 1)
{
int mid = (hi + lo)/2;
int midcomp = x[mid].compareTo (a);
if (midcomp == 0)
{
return mid;
}
else if (midcomp < 0)
{
lo = mid;
locomp = midcomp;
}
else
{
hi = mid;
hicomp = midcomp;
}
}
return locomp == 0 ? lo : hicomp == 0 ? hi : -1;
}
// Unit test main program.
// /**
// * Unit test main program.
// *
// * Usage: java edu.rit.util.Searching a x_elements
// *
a = Element to be searched for
// *
x_elements = Array elements to be searched
// */
// public static void main
// (String[] args)
// {
// if (args.length < 1) usage();
// int a = java.lang.Integer.parseInt (args[0]);
// int n = args.length - 1;
// int[] x = new int [n];
// for (int i = 0; i < n; ++ i)
// x[i] = java.lang.Integer.parseInt (args[i+1]);
// Searching.Integer helper = new Searching.Integer();
// System.out.printf ("searchUnsorted() returns %d%n",
// Searching.searchUnsorted (x, a, helper));
// System.out.printf ("searchSorted() returns %d%n",
// Searching.searchSorted (x, a, helper));
// }
//
// /**
// * Print a usage message and exit.
// */
// private static void usage()
// {
// System.err.println ("Usage: java edu.rit.util.Searching ");
// System.err.println (" = Element to be searched for");
// System.err.println (" = Array elements to be searched");
// System.exit (1);
// }
}