forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinarySearch.java
More file actions
71 lines (54 loc) · 1.63 KB
/
Copy pathBinarySearch.java
File metadata and controls
71 lines (54 loc) · 1.63 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.Scanner;
/**
*
* @author Varun Upadhyay (https://github.com/varunu28)
*
*/
class BinarySearch
{
/**
* This method implements the Generic Binary Search
*
* @param array The array to make the binary search
* @param key The number you are looking for
* @param lb The lower bound
* @param ub The upper bound
* @return the location of the key
**/
public static <T extends Comparable<T>> int BS(T array[], T key, int lb, int ub)
{
if ( lb > ub)
return -1;
int mid = (ub+lb) >>> 1;
int comp = key.compareTo(array[mid]);
if (comp < 0)
return (BS(array, key, lb, mid-1));
if (comp > 0)
return (BS(array, key, mid + 1, ub));
return mid;
}
// Driver Program
public static void main(String[] args)
{
Scanner input=new Scanner(System.in);
// For INTEGER Input
Integer[] array = new Integer[10];
int key = 5;
for (int i = 0; i < 10 ; i++ )
array[i] = i+1;
int index = BS(array, key, 0, 9);
if (index != -1)
System.out.println("Number " + key + " found at index number : " + index);
else
System.out.println("Not found");
// For STRING Input
String[] array1 = {"a", "b", "c", "d", "e"};
String key1 = "d";
int index1 = BS(array1, key1, 0, array1.length-1);
if (index1 != -1)
System.out.println("String " + key1 + " found at index number : " + index1);
else
System.out.println("Not found");
input.close();
}
}