public class SearchTest {
public static void main(String[] args) {
Search s = new Search();
// int arr[]= {0,2,3,4,12,23,23,23,23,23,23,23,23,23,23,23,23};
// Set resIndexSet=s.binarySearch2(arr, 23, 0, arr.length-1);
// System.out.println(resIndexSet);
int arr[] = new int[100];
for (int i = 0; i < 100; i++) {
arr[i] = i + 1;
}
System.out.println(“二分查找” + s.binarySearch(arr, 100, 0, arr.length - 1));
Set resIndexSet1 = s.binarySearch2(arr, 100, 0, arr.length - 1);
System.out.println(“二分查找” + resIndexSet1);
Set resIndexSet2 = s.interpolationSearch(arr, 100, 0, arr.length - 1);
System.out.println(“插值查找” + resIndexSet2);
}
}

class Search {
// 二分查找
public int binarySearch(int arr[], int number, int left, int right) {
if (left > right || arr[left] > number || arr[right] < number) {
return -1;
}
int middle = (left + right) / 2;
if (arr[middle] > number) {
return binarySearch(arr, number, left, middle - 1);
} else if (arr[middle] < number) {
return binarySearch(arr, number, middle + 1, right);
} else {
return middle;
}
}

// 二分查找（如果有重复的就全部输出）
public Set<Integer> binarySearch2(int arr[], int number, int left, int right) {
	if (left > right || arr[left] > number || arr[right] < number) {
		return new TreeSet<Integer>();
	}
	int middle = (left + right) / 2;
	Set<Integer> resIndexSet = new TreeSet<Integer>();
	if (arr[middle] > number) {
		return binarySearch2(arr, number, left, middle - 1);
	} else if (arr[middle] < number) {
		return binarySearch2(arr, number, middle + 1, right);
	} else {
		int temp = middle - 1;
		while (true) {
			if (arr[temp] != number || temp < 0) {
				break;
			}
			resIndexSet.add(temp);
			temp--;
		}
		resIndexSet.add(middle);
		temp = middle + 1;
		while (true) {
			if (temp > arr.length - 1 || arr[temp] != number) {
				break;
			}
			resIndexSet.add(temp);
			temp++;
		}
		return resIndexSet;
	}
}

// 插值查找
public Set<Integer> interpolationSearch(int arr[], int number, int left, int right) {
	if (left > right || arr[left] > number || arr[right] < number) {
		return new TreeSet<Integer>();
	}
	int middle = left + (number - arr[left]) / (arr[right] - arr[left]) * (right - left);
	Set<Integer> resIndexSet = new TreeSet<Integer>();
	if (arr[middle] > number) {
		return interpolationSearch(arr, number, left, middle - 1);
	} else if (arr[middle] < number) {
		return interpolationSearch(arr, number, middle + 1, right);
	} else {
		int temp = middle - 1;
		while (true) {
			if (arr[temp] != number || temp < 0) {
				break;
			}
			resIndexSet.add(temp);
			temp--;
		}
		resIndexSet.add(middle);
		temp = middle + 1;
		while (true) {
			if (temp > arr.length - 1 || arr[temp] != number) {
				break;
			}
			resIndexSet.add(temp);
			temp++;
		}
		return resIndexSet;
	}
}
}

}