forked from examplehub/Java
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathBinarySearch.java
More file actions
55 lines (51 loc) · 1.48 KB
/
BinarySearch.java
File metadata and controls
55 lines (51 loc) · 1.48 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package com.examplehub.searches;
import com.examplehub.maths.MiddleIndexCalculate;
public class BinarySearch implements Search {
/**
* Binary search algorithm.
*
* @param numbers the numbers to be searched.
* @param key the key to be searched.
* @return index of {@code key} value if found, otherwise -1.
*/
@Override
public int search(int[] numbers, int key) {
int left = 0;
int right = numbers.length - 1;
while (left <= right) {
int mid = MiddleIndexCalculate.middle(left, right);
if (key == numbers[mid]) {
return mid;
} else if (key > numbers[mid]) {
left = mid + 1; /* search at right sub array */
} else {
right = mid - 1; /* search at left sub array */
}
}
return -1;
}
/**
* Generic binary search algorithm.
*
* @param array the array to be searched.
* @param key the key object to be searched.
* @param <T> the class of the objects in the array.
* @return index of {@code key} if found, otherwise -1.
*/
@Override
public <T extends Comparable<T>> int search(T[] array, T key) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (key.compareTo(array[mid]) == 0) {
return mid;
} else if (key.compareTo(array[mid]) > 0) {
left = mid + 1; /* search at right sub array */
} else {
right = mid - 1; /* search at left sub array */
}
}
return -1;
}
}