二分探索の復習。java.util.Arrays#binarySearch
は検索対象の要素が複数あった場合、どれの位置を返すか保証しない。
最初の位置を返したい場合は、対象の要素が見つかっても右側のポインタを左に進め続け、ループを抜けたときの右側のポインタの位置が答え。
最後の位置を返したい場合は、対象の要素が見つかっても左側のポインタを右進め続け、ループを抜けたときの左側のポインタの位置が答え。
簡単そうで少し難しい。
import java.util.Arrays;
public class BinarySearch {
// 最初の要素の位置を返す
public static int binarySearch(int[] arr, int key) {
int i = -1, j = arr.length - 1;
while (i + 1 != j) {
int m = i + (j - i) / 2;
if (arr[m] < key) {
i = m;
} else {
j = m;
}
}
if (arr[j] == key) {
return j;
}
return -1;
}
// 最後の要素の位置を返す
public static int binarySearch2(int[] arr, int key) {
int i = 0, j = arr.length;
while (i + 1 != j) {
int m = i + (j - i) / 2;
if (arr[m] <= key) {
i = m;
} else {
j = m;
}
}
if (arr[i] == key) {
return i;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 3, 3, 3, 3, 3, 4, 5, 6};
System.out.println(Arrays.binarySearch(arr, 3));
System.out.println(binarySearch(arr, 3));
System.out.println(binarySearch2(arr, 3));
}
}
実行結果
5
2
7
応用編。配列が回転した場合。
public class BinarySearchCustomized {
private static int find(int[] arr, int v, int i, int j) {
if (j < i) {
return -1;
}
int m = i + (j - i) / 2;
if (arr[m] == v) {
return m;
} else if (arr[i] == v) {
return i;
} else if (arr[j] == v) {
return j;
}
/*
|---------------|--------------------|
i m ^ j
|---------------|--------------------|
i ^ m j
|---------------|--------------------|
i m ^ j
*/
if (v > arr[m]) {
if (arr[m] <= arr[j]) {
if (v < arr[j]) {
return find(arr, v, m, j);
} else {
return find(arr, v, i, m);
}
} else {
return find(arr, v, m, j);
}
}
/*
|---------------|--------------------|
i ^ m j
|---------------|--------------------|
i m ^ j
|---------------|--------------------|
i ^ m j
*/
if (v < arr[m]) {
if (arr[m] <= arr[j]) {
return find(arr, v, i, m);
} else {
if (v < arr[j]) {
return find(arr, v, m, j);
} else {
return find(arr, v, i, m);
}
}
}
return -1;
}
public static int search(int[] arr, int v) {
return find(arr, v, 0, arr.length - 1);
}
public static void main(String[] args) {
int[] arr = {15, 16, 19, 20, 25, 30, 100, 200, 1, 2, 3, 4, 5, 7, 10, 11, 12, 14};
for (int i = 0; i < arr.length; i++) {
System.out.println(search(arr, arr[i]));
}
}
}