1 /* 2 * Copyright 2013, Google Inc. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * * Redistributions in binary form must reproduce the above 12 * copyright notice, this list of conditions and the following disclaimer 13 * in the documentation and/or other materials provided with the 14 * distribution. 15 * * Neither the name of Google Inc. nor the names of its 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 package org.jf.util; 33 34 import java.util.Comparator; 35 import java.util.List; 36 37 public class LinearSearch { 38 /** 39 * Performs a linear search in a sorted list for key, starting at initialGuess 40 * 41 * @param list The sorted list to search 42 * @param comparator The comparator to use 43 * @param key The key to search for 44 * @param initialGuess An initial guess of the location. 45 * @return If found, the index of the item. If not found, -return + 1 is the index at which the item would be 46 * inserted 47 */ linearSearch(List<? extends T> list, Comparator<T> comparator, T key, int initialGuess)48 public static <T> int linearSearch(List<? extends T> list, Comparator<T> comparator, T key, int initialGuess) { 49 int guess = initialGuess; 50 if (guess >= list.size()) { 51 guess = list.size()-1; 52 } 53 int comparison = comparator.compare(list.get(guess), key); 54 if (comparison == 0) { 55 return guess; 56 } 57 if (comparison < 0) { 58 guess++; 59 while (guess < list.size()) { 60 comparison = comparator.compare(list.get(guess), key); 61 if (comparison == 0) { 62 return guess; 63 } 64 if (comparison > 0) { 65 return -(guess+1); 66 } 67 guess++; 68 } 69 return -(list.size()+1); 70 } else { 71 guess--; 72 while (guess >= 0) { 73 comparison = comparator.compare(list.get(guess), key); 74 if (comparison == 0) { 75 return guess; 76 } 77 if (comparison < 0) { 78 return -(guess+2); 79 } 80 guess--; 81 } 82 return -1; 83 } 84 } 85 } 86