-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinarySearch.java
More file actions
104 lines (90 loc) · 3.24 KB
/
binarySearch.java
File metadata and controls
104 lines (90 loc) · 3.24 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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public class binarySearch {
static int binarysearch(int arr[], int n, int k) {
int low = 0;
int high = n-1;
while (low <= high) {
int mid = (high + low) / 2;
System.out.println("21mid: " + mid);
System.out.println("22low: " + low);
System.out.println("23high: " + high);
System.out.println("24arr[mid]: " + arr[mid]);
if (arr[mid] == k) {
return mid;
} else if (arr[mid] < k) {
low = mid + 1;
System.out.println("29low: " + low);
} else {
high = mid - 1;
System.out.println("31high: " + high);
}
}
return -1;
}
public static void main(String[] args) {
int arr[] = {1, 2, 3, 4, 5};
int n = 5;
int k = 4;
// int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}; //12
// int n = 15;
// int k = 13;
// mid = 8
// mid = mid + 15 - 8 / 2; 11; low = 8
// mid = low = 11; mid(11) + 4/2 = 13
// mid = high = 13;
// int arr[] = {11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 121, 133, 144};
// mid = 13/2 = 6
// mid = 6 + (13-6/2) = 9; arr[9] = 111
// mid = 9 + (13 - 9)/2 = 11; arr[11] = 133
// mid = 11 (133); + (13 - 11)/2 = 12
// int n = 16;
// int k = 121;
// int arr[] = {11, 22, 33, 44, 55};
// int n = 5;
// int k = 445;
// int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 17, 18, 19, 20, 21, 22, 25, 26, 27, 29, 31, 32, 33, 35, 36, 40, 41, 42, 43, 46, 47, 48, 51, 54, 55, 56, 57, 58, 61, 63, 64, 65, 67, 69, 71, 74, 77, 78, 79, 80, 81, 82, 83, 85, 86, 87, 88, 89, 90, 91, 93, 95, 99, 100};
// int n = 68;
// int k = 99;
System.out.println("Output: " + binarysearch(arr, n, k));
}
}
// code here
// find midpoint of arr
// is midpoint == k; return index + 1
// if mid < k, search on right
// search fails if:
// {0, 1, 2, 3, 4, 5, 6, 8, 9, 10}; k = 7
// k is out of bounds
// G4G: initial left, right, middle
// while left < right, define middle
// Check if array[middle] == k, return middle
// if arr[m] < x, left = middle + 1
// else right = middle - 1
// else return -1
/*
* https://www.geeksforgeeks.org/problems/binary-search-1587115620/1?page=1&difficulty=Basic&sortBy=submissions
* Given a sorted array of size N and an integer K, find the position(0-based indexing) at which K is present in
* the array using binary search.
Example 1:
Input:
N = 5
arr[] = {1 2 3 4 5}
K = 4
Output: 3
Explanation: 4 appears at index 3.
Example 2:
Input:
N = 5
arr[] = {11 22 33 44 55}
K = 445
Output: -1
Explanation: 445 is not present.
Your Task:
You dont need to read input or print anything. Complete the function binarysearch() which takes arr[], N and K
as input parameters and returns the index of K in the array. If K is not present in the array, return -1.
Expected Time Complexity: O(LogN)
Expected Auxiliary Space: O(LogN) if solving recursively and O(1) otherwise.
Constraints:
1 <= N <= 105
1 <= arr[i] <= 106
1 <= K <= 106
*/