KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > rcm > util > BinarySearch


1 /*
2  * Copyright (c) 1998-2002 Carnegie Mellon University. All rights
3  * reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1. Redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer.
11  *
12  * 2. Redistributions in binary form must reproduce the above copyright
13  * notice, this list of conditions and the following disclaimer in
14  * the documentation and/or other materials provided with the
15  * distribution.
16  *
17  * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
18  * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
19  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
21  * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  *
29  */
30
31 package rcm.util;
32
33 /**
34  * Binary search routines.
35  */
36 public abstract class BinarySearch {
37     public static Debug debug = Debug.QUIET;
38
39     /**
40      * Search a sorted array of integers.
41      * @param array Array of integers
42      * @param offset Starting offset of subarray to search
43      * @param length Length of subarray to search
44      * @param x Value to search for
45      * @return largest index i in subarray (offset <= i <= offset+length)
46      * such that all elements below i in the subarray are strictly less
47      * than x. If x is found in the subarray, then array[i] == x (and i is
48      * the first occurence of x in the subarray). If x is not found,
49      * then array[i] is where x should be inserted in the sort order.
50      */
51     public static int search (int[] array, int offset, int length, int x) {
52         // handle 0-length subarray case right away
53 if (length <= 0)
54             return offset;
55
56         int low = offset;
57         int high = offset+length-1;
58         // since length > 0, array[low] and array[high] are valid indices
59
60         if (x <= array[low])
61             return low;
62         if (x > array[high])
63             return high+1;
64         
65         while (low+1 < high) {
66             // loop invariant: array[low] < x <= array[high],
67 // offset <= low < high < offset+length
68 int mid = (low + high)/2;
69             if (x <= array[mid])
70                 high = mid;
71             else
72                 low = mid;
73         }
74         // now we have array[low] < x <= array[high]
75 // && (low+1 == high || low == high)
76 // implies low+1 == high
77 debug.assertion (low+1 == high);
78         return high;
79     }
80 }
81
Popular Tags