01: /*
02: * Licensed to the Apache Software Foundation (ASF) under one or more
03: * contributor license agreements. See the NOTICE file distributed with
04: * this work for additional information regarding copyright ownership.
05: * The ASF licenses this file to You under the Apache License, Version 2.0
06: * (the "License"); you may not use this file except in compliance with
07: * the License. You may obtain a copy of the License at
08: *
09: * http://www.apache.org/licenses/LICENSE-2.0
10: *
11: * Unless required by applicable law or agreed to in writing, software
12: * distributed under the License is distributed on an "AS IS" BASIS,
13: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14: * See the License for the specific language governing permissions and
15: * limitations under the License.
16: */
17:
18: package org.apache.harmony.luni.util;
19:
20: public class BinarySearch {
21:
22: /**
23: * Search the sorted characters in the string and return an exact index or
24: * -1.
25: *
26: * @param data
27: * the String to search
28: * @param value
29: * the character to search for
30: * @return the matching index, or -1
31: */
32: public static int binarySearch(String data, char value) {
33: int low = 0, high = data.length() - 1;
34: while (low <= high) {
35: int mid = (low + high) >> 1;
36: char target = data.charAt(mid);
37: if (value == target)
38: return mid;
39: else if (value < target)
40: high = mid - 1;
41: else
42: low = mid + 1;
43: }
44: return -1;
45: }
46:
47: /**
48: * Search the sorted characters in the string and return the nearest index.
49: *
50: * @param data
51: * the String to search
52: * @param c
53: * the character to search for
54: * @return the nearest index
55: */
56: public static int binarySearchRange(String data, char c) {
57: char value = 0;
58: int low = 0, mid = -1, high = data.length() - 1;
59: while (low <= high) {
60: mid = (low + high) >> 1;
61: value = data.charAt(mid);
62: if (c > value)
63: low = mid + 1;
64: else if (c == value)
65: return mid;
66: else
67: high = mid - 1;
68: }
69: return mid - (c < value ? 1 : 0);
70: }
71: }
|