二分法は、条件を満たす最初のアイテムを検索します.
3079 ワード
public class BinSearch1st {
Random random = new Random();
/**
* , s , -1
* @param arr
* @param s
* @return
*/
public int bsearch(int[] arr, int s) {
int left = 0;
int right = arr.length - 1;
int cur = 0;
while (left <= right) {
cur = (left + right) >>> 1;
if (arr[cur] > s) {
right = cur - 1;
} else if (arr[cur] < s) {
left = cur + 1;
} else {
return cur;
}
}
return -1;
}
/**
* s , -1
* @param arr
* @param s
* @return
*/
public int search(int[] arr, int s) {
int leftM = 0;
int left = 0;
int right = arr.length - 1;
int cur = 0;
while (left <= right) {
cur = (left + right) >>> 1;
if (arr[cur] > s) {
right = cur - 1;
} else if (arr[cur] < s) {
left = cur + 1;
leftM = left;
} else {
if (arr[leftM] == arr[cur]) {//
return leftM;
} else if (leftM < cur && arr[leftM] < arr[cur] && left < right) {
right = cur;
} else {
return cur;
}
}
}
return -1;
}
@Test
public void test() {
int len = 10 + random.nextInt(100);
int[] arr = new int[len];
for (int i=0; i<len; i++) {
arr[i] = random.nextInt(len);
}
Arrays.sort(arr);
int s = arr[random.nextInt(len)];
int i = search(arr, s);
int j = 0;
for (; j<len; j++) {
if (arr[j] == s) {
break;
}
}
System.out.println(Arrays.toString(arr));
System.out.println(i + " : " + arr[i] + " : " + s + " : " + j);
Assert.assertEquals(j, i);
int bs = bsearch(arr, s);
Assert.assertEquals(s, arr[bs]);
s = len;
i = search(arr, s);
bs = bsearch(arr, s);
Assert.assertEquals(-1, i);
Assert.assertEquals(-1, bs);
}
public static void main(String[] args) {
BinSearch1st b = new BinSearch1st();
for (int i=0; i<100; i++)
b.test();
}
}