modules/luni/src/main/java/org/apache/harmony/luni/util/BinarySearch.java

/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

package org.apache.harmony.luni.util;


public class BinarySearch {

	/**
	 * Search the sorted characters in the string and return an exact index or
	 * -1.
	 * 
	 * @param data
	 *            the String to search
	 * @param value
	 *            the character to search for
	 * @return the matching index, or -1
	 */
	public static int binarySearch(String data, char value) {
		int low = 0, high = data.length() - 1;
		while (low <= high) {
			int mid = (low + high) >> 1;
			char target = data.charAt(mid);
			if (value == target)
				return mid;
			else if (value < target)
				high = mid - 1;
			else
				low = mid + 1;
		}
		return -1;
	}

	/**
	 * Search the sorted characters in the string and return the nearest index.
	 * 
	 * @param data
	 *            the String to search
	 * @param c
	 *            the character to search for
	 * @return the nearest index
	 */
	public static int binarySearchRange(String data, char c) {
		char value = 0;
		int low = 0, mid = -1, high = data.length() - 1;
		while (low <= high) {
			mid = (low + high) >> 1;
			value = data.charAt(mid);
			if (c > value)
				low = mid + 1;
			else if (c == value)
				return mid;
			else
				high = mid - 1;
		}
		return mid - (c < value ? 1 : 0);
	}
}