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