javaのバイナリサーチ。これは書籍のほぼ丸写し。
import java.util.*;
import java.io.BufferedReader;
class BinarySearch {
private static int binarySearch (int target, int[] numbers) {
int left = 0;
int right = numbers.length - 1;
int center;
while (left <= right) {
center = (left + right) / 2;
System.out.println("centrt: " + center);
if (numbers[center] == target) {
return center;
}
if (numbers[center] < target) {
left = center + 1;
} else {
right = center - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] numbers = new int[20];
Random random = new Random();
for (int i = 0; i < numbers.length; ++i) {
numbers[i] = random.nextInt(10);
}
Arrays.sort(numbers);
for (int i = 0; i < numbers.length; ++i) {
System.out.println(numbers[i]);
}
System.out.println("\nWhat do you search for?");
int target = intReader();
int result = binarySearch(target, numbers);
if (result == -1) {
System.out.println(target + "is not found...");
} else {
System.out.println(target + " is found at " + (result + 1));
}
}
private static int intReader() {
try {
BufferedReader read = new BufferedReader(new java.io.InputStreamReader(System.in));
String str = read.readLine();
return Integer.parseInt(str);
} catch (java.io.IOException e) {
System.err.println("IO exception");
return 0;
} catch (NumberFormatException e) {
return 0;
}
}
}
ruby版のバイナリサーチ。
def binary_search(target, numbers)
left = 0
right = numbers.length - 1
center = nil
while left <= right do
center = (left + right) / 2
puts center
if numbers[center] == target
return center
end
if numbers[center] < target
left = center + 1
else
right = center - 1
end
end
return -1
end
numbers = []
20.times { numbers << rand(100) }
numbers.sort!
j = 0
numbers.each do |number|
puts "#{j} : #{number}"
j = j + 1
end
puts "What do you search for?"
target = STDIN.gets.chomp
search_result = binary_search(target.to_i, numbers)
if search_result == -1
puts "Could not found anything that matches \"#{target}\""
else
puts "#{target} is found at #{search_result}"
end