Custom Binary Search

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);
 }
}

• Tweet
• Share
• Share
• Share
• Share

About Kartik Chandra Mandal

I am Kartik Chandra Mandal from Bangalore, India. Working as software engineer in Java technology. Have good knowledge of OWASP and CSRF in security for applications and it's implementation in Java technology.

Related Post