Finding mid
Wrong: mid = (high + low) / 2
Correct: mid = low + (high-low)/2
Consider case where high=-4 and low=-5, mid will be -4 which is high, so it will keep looping because you cannot reduce high value.
Finding exact value
Where the exact value must be find
Inclusive version stop at low > high, while exclusive version stop at low == high.
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
| private int iterativeInclusive(){
int low = 0, high = nums.length-1;
while(low <= high){
int mid = low + (high-low)/2;
if(nums[mid] == target){
return mid;
}
if(nums[mid] < target)
low = mid+1;
else
high = mid-1;
}
return -1;
}
private int iterativeExclusive(){
int low = 0, high = nums.length;
while(low < high){
int mid = low + (high-low)/2;
if(nums[mid] == target){
return mid;
}
if(nums[mid] < target)
low = mid+1;
else
high = mid;
}
return -1;
}
|
Refer: Binary Search
Finding floor value or ceiling value
Better use inclusive high version.
For exclusive version, you have to search range says (0, 2),
then it can stucks with (0, 2) forever, because you can only assign end with mid+1, which is the end itself, no progress is made, so I have to handle arrays of length 2 also as base case.
1
2
3
4
5
6
7
8
9
10
| private int findK(long low, long high){
if(low == high) return (int) low;
long mid = low+(high-low)/2; //fuck!! there introduce a bug, consider case -5, -4.
int cnt = count(mid);
if(cnt < k)
return findK(mid+1, high);
else
return findK(low, mid);
}
|
Refer: Kth Smallest Element in a Sorted Matrix
Refer: Search Insert Position
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| //This is the example of finding higest value
int low, high, mid;
low = 0;
high = s.length()-1;
int lastGoodS = -1;
//low and high inclusive
while(low < high){
mid = low + (high-low+1)/2;
int spos = checkHaveDuplicate(mid);
if(spos != -1){
low = mid;
lastGoodS = spos;
}
else{
high = mid-1;
}
}
|
Refer: Longest Duplicate Substring
Binary search using library function
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
| //exact value, just use the binarySearch and check for pos is positive.
private int searchGEq(long[] arr, int start, int end, long value){
int pos = Arrays.binarySearch(arr, start, end, value);
if(pos >=0){
//ensure it is the leftmost [value, ..)
while(pos-1 >=start && arr[pos-1] == value) --pos;
return pos;
}
else{
//this is the insert position
// 0 1 3, search for 2, I want to return 3
// ^
return -(pos+1);
}
}
private int searchLEq(long[] arr, int start, int end, long value){
int pos = Arrays.binarySearch(arr, start, end, value);
if(pos >=0){
//ensure it is the rightmost (... value]
while(pos+1 < end && arr[pos+1] == value) ++pos;
return pos;
}
else{
// 0 1 3, search for 2, I want to return 1
// ^
return -(pos+1)-1;
}
}
|
Searching in sorted 2D array
The top-right or left-bottom corner search approach is O(sqrt(K)) search algorithm on the linear version.
Time complexity: O(M+N)
Binary search tree
1
| //TODO: to be completed
|
Searching on K-dimension
This is the extension of BST in higher dimension
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| class KDTree{
int[][] points;
Node root;
int dimension;
int N;
Random r;
public KDTree(int dimension){
this.dimension = dimension;
}
public void add(int[] point){
root = addHelper(point, root, 0);
}
public Node addHelper(int[] point, Node cur, int lvl){
if(cur == null)
return new Node(point, lvl % dimension);
if(point[cur.dim] < cur.value[cur.dim] ){
cur.left = addHelper(point, cur.left, lvl+1);
}
else{
cur.right = addHelper(point, cur.right, lvl+1);
}
return cur;
}
//how to find k nearest
PriorityQueue<Tuple> pq;
int k = -1;
public int[][] kNearestPoint(int[] point, int k){
pq = new PriorityQueue<>();
this.k = k;
kNearestPointHelper(point, root);
int[][] result = new int[k][];
for(int i=0; i<k; ++i)
result[i] = pq.poll().point;
return result;
}
public void kNearestPointHelper(int[] point, Node curr){
if(curr == null) return;
//System.out.println("T: " + curr.value[0] + "," + curr.value[1]);
int cv = point[curr.dim];
//find the dist between root.
long curDist = dist(point, curr.value);
if(pq.size() < k){
pq.offer(new Tuple(curDist, curr.value) );
}
else if(pq.peek().dist > curDist){
pq.poll();
pq.offer(new Tuple(curDist, curr.value) );
}
if(cv >= curr.value[curr.dim]){
kNearestPointHelper(point, curr.right);
//traverse also left?
long distBoundBoxOther = point[curr.dim] - curr.value[curr.dim];
distBoundBoxOther = distBoundBoxOther * distBoundBoxOther;
if(pq.size() < k || distBoundBoxOther < pq.peek().dist ){
kNearestPointHelper(point, curr.left);
}
}
else {
kNearestPointHelper(point, curr.left);
//traverse also left?
long distBoundBoxOther = point[curr.dim] - curr.value[curr.dim];
distBoundBoxOther = distBoundBoxOther * distBoundBoxOther;
if(pq.size() < k || distBoundBoxOther < pq.peek().dist ){
kNearestPointHelper(point, curr.right);
}
}
}
private long dist(int[] pt1, int[] pt2){
long diffX = pt1[0] -pt2[0];
long diffY = pt1[1] -pt2[1];
return diffX * diffX + diffY * diffY;
}
}
class Node{
public int[] value;
public int dim;
public Node left;
public Node right;
public Node(int[] v, int d){
value = v;
dim = d;
}
}
class Tuple implements Comparable<Tuple>{
public long dist;
public int[] point;
public Tuple(long d, int[] p){
dist = d;
point = p;
}
public int compareTo(Tuple t){
if(dist == t.dist)
return 0;
else if(dist < t.dist) return 1;
else return -1;
}
}
|
Reference:
K Closest Points to Origin
Queries on Number of Points Inside a Circle