A generic binary search algorithm on a List in Java, with
optimizations for handling large lists and distinguishing between RandomAccess
lists and others. Here’s a breakdown of the key components of the code:
java
|
package
com.kartik;
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
import java.util.RandomAccess;
/**
*
* @author MandalKC
*
*/
public class BinarySearch {
private static final int BINARYSEARCH_THRESHOLD = 5000;
/**
*
* @param list
* @param key
* @return
*/
public static <T> int binarySearch(
List<? extends Comparable<? super T>> list, T
key) {
if (list instanceof RandomAccess
|| list.size() < BINARYSEARCH_THRESHOLD)
return indexedBinarySearch(list, key);
else
return iteratorBinarySearch(list, key);
}
/**
*
* @param list
* @param key
* @return
*/
private static <T> int indexedBinarySearch(
List<? extends Comparable<? super T>> list, T
key) {
int low = 0;
int high = list.size() - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable<? super T> midVal = list.get(mid);
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found
}
/**
*
* @param list
* @param key
* @return
*/
private static <T> int iteratorBinarySearch(
List<? extends Comparable<? super T>> list, T
key) {
int low = 0;
int high = list.size() - 1;
ListIterator<? extends Comparable<? super T>> i =
list.listIterator();
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable<? super T> midVal = get(i, mid);
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found
}
/**
*
* @param i
* @param index
* @return
*/
private static <T> T get(ListIterator<? extends T> i, int
index) {
T obj = null;
int pos = i.nextIndex();
if (pos <= index) {
do {
obj = i.next();
} while (pos++ < index);
} else {
do {
obj = i.previous();
} while (--pos > index);
}
return obj;
}
/**
*
* @param args
*/
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("kartik");
list.add("Mandal");
list.add("Java");
list.add("J2EE");
list.add("Maza");
list.add("JSP");
list.add("Spring");
list.add("Hibernate");
list.add("Maven");
list.add("Mocha");
list.add("Host");
String key = "Maven";
binarySearch(list, key);
}
}
|
Key Features:
- Two
Types of Binary Search:
Ø
indexedBinarySearch: Used when the list
supports fast random access, i.e., RandomAccess lists like ArrayList.
Ø
iteratorBinarySearch: Used for non-RandomAccess
lists or when the list size exceeds a certain threshold, using an iterator for
traversal, which is more efficient for linked structures like LinkedList.
- Threshold
(BINARYSEARCH_THRESHOLD):
Ø
If the list size is below this threshold, the
indexed binary search is used, otherwise iterator-based search is applied.
- Binary
Search Logic:
Ø
The binary search itself follows a standard
procedure:
ü
Find the middle of the list.
ü
Compare the middle element with the search key.
ü
Adjust the search range (low and high indices)
based on comparison results.
ü
If the key is found, return its position.
ü
If not found, return a negative value indicating
where the key would have been inserted.
 |
| Custom Binary Search |
0 Comments