Admin: 1 версия

2010-06-01T05:04:10Z

1 версия

в 17:44, 31 мая 2010

2010-05-31T17:44:27Z

Новая страница

== Binary search ==



<source lang="java">
import java.util.Arrays;
import java.util.Random;
public class MainClass {
private static int[] data = new int[10]; // create space for array
public static void main(String[] args) {
Random generator = new Random();
for (int i = 0; i < 10; i++)
data[i] = 10 + generator.nextInt(90);
Arrays.sort(data);
System.out.println(binarySearch(3));
}
public static int binarySearch(int searchElement) {
int low = 0;
int high = data.length - 1;
int middle = (low + high + 1) / 2;
int location = -1;
do {
System.out.print(remainingElements(low, high));
for (int i = 0; i < middle; i++)
System.out.print(" ");
System.out.println(" * ");
if (searchElement == data[middle])
location = middle;
else if (searchElement < data[middle])
high = middle - 1;
else
low = middle + 1;
middle = (low + high + 1) / 2;
} while ((low <= high) && (location == -1));
return location;
}
public static String remainingElements(int low, int high) {
StringBuffer temporary = new StringBuffer();
for (int i = 0; i < low; i++)
temporary.append(" ");
for (int i = low; i <= high; i++)
temporary.append(data[i] + " ");
temporary.append("\n");
return temporary.toString();
}
}</source>



<pre class=codeResult>16 20 31 58 64 75 83 85 86 96
*
16 20 31 58 64
*
16 20
*
16
*
-1</pre>

== Recursive Binary Search Implementation in Java ==



<source lang="java">
public class Main {
public static final int NOT_FOUND = -1;
public static int binarySearch(Comparable[] a, Comparable x) {
return binarySearch(a, x, 0, a.length - 1);
}
private static int binarySearch(Comparable[] a, Comparable x, int low, int high) {
if (low > high)
return NOT_FOUND;
int mid = (low + high) / 2;
if (a[mid].rupareTo(x) < 0)
return binarySearch(a, x, mid + 1, high);
else if (a[mid].rupareTo(x) > 0)
return binarySearch(a, x, low, mid - 1);
else
return mid;
}
public static void main(String[] args) {
int SIZE = 8;
Comparable[] a = new Integer[SIZE];
for (int i = 0; i < SIZE; i++)
a[i] = new Integer(i * 2);
for (int i = 0; i < SIZE * 2; i++)
System.out.println("Found " + i + " at " + binarySearch(a, new Integer(i)));
}
}</source>

← Предыдущая	Версия 05:04, 1 июня 2010
(нет различий)

Java Tutorial/Collections/Search - История изменений

Admin: 1 версия

в 17:44, 31 мая 2010