01: /*
02: * Copyright (c) 1998-2002 Carnegie Mellon University. All rights
03: * reserved.
04: *
05: * Redistribution and use in source and binary forms, with or without
06: * modification, are permitted provided that the following conditions
07: * are met:
08: *
09: * 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: }
|