78 lines
2.0 KiB
Java
78 lines
2.0 KiB
Java
package search;
|
|
|
|
/**
|
|
* @author Nikita Doschennikov (me@fymio.us)
|
|
*/
|
|
public class BinarySearch3839 {
|
|
|
|
public static void main(String[] args) {
|
|
IntList a = new IntList();
|
|
int x = Integer.parseInt(args[0]);
|
|
int n = args.length;
|
|
for (int i = 1; i < n; i++) {
|
|
a.put(Integer.parseInt(args[i]));
|
|
}
|
|
|
|
int leftBound = leftBoundIterative(x, a);
|
|
int rightBound = rightBoundIterative(x, a);
|
|
int range = rightBound - leftBound;
|
|
System.out.println(leftBound + " " + range);
|
|
}
|
|
|
|
static int leftBoundIterative(int x, IntList a) {
|
|
int low = 0,
|
|
high = a.getLength() - 1;
|
|
while (low <= high) {
|
|
int mid = low + (high - low) / 2;
|
|
if (a.get(mid) > x) {
|
|
low = mid + 1;
|
|
} else {
|
|
high = mid - 1;
|
|
}
|
|
}
|
|
return high + 1;
|
|
}
|
|
|
|
static int rightBoundIterative(int x, IntList a) {
|
|
int low = 0,
|
|
high = a.getLength() - 1;
|
|
while (low <= high) {
|
|
int mid = low + (high - low) / 2;
|
|
if (a.get(mid) >= x) {
|
|
low = mid + 1;
|
|
} else {
|
|
high = mid - 1;
|
|
}
|
|
}
|
|
return high + 1;
|
|
}
|
|
|
|
static int leftBoundRecursive(int x, IntList a, int low, int high) {
|
|
if (low > high) {
|
|
return high + 1;
|
|
}
|
|
|
|
int mid = low + (high - low) / 2;
|
|
|
|
if (a.get(mid) > x) {
|
|
return leftBoundRecursive(x, a, mid + 1, high);
|
|
} else {
|
|
return leftBoundRecursive(x, a, low, mid - 1);
|
|
}
|
|
}
|
|
|
|
static int rightBoundRecursive(int x, IntList a, int low, int high) {
|
|
if (low > high) {
|
|
return high + 1;
|
|
}
|
|
|
|
int mid = low + (high - low) / 2;
|
|
|
|
if (a.get(mid) >= x) {
|
|
return rightBoundRecursive(x, a, mid + 1, high);
|
|
} else {
|
|
return rightBoundRecursive(x, a, low, mid - 1);
|
|
}
|
|
}
|
|
}
|