LeetCode - The Binary Search Part
This part is for Binary Search.
The binary search is a method to search in a given range. Basically, if we meet a problem wants to find something. Then we can try binary search.
There are something need to be mentioned.
First, there are three different binary search.
- exact search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int binarySearch(int[] arr, int target){
int low = 0, high = arr.length - 1;
// must be <= so that won't miss low == high case.
while (low <= high){
int mid = low + (high - low) / 2;
if (arr[mid] == target){
return mid;
}
else if (arr[mid] < target){
low = mid+1;
}
else{
high = mid - 1;
}
}
return -1;
}
- ceiling search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int ceilingSearch(int[] arr, int target){
// what if all items in arr is lower than target?
// if we want to find insert position then high should be arr.length
int low = 0, high = arr.length;
while(low < high){
int mid = low + (high - low) / 2;
if (arr[mid] == target){
return mid;
}
else if (arr[mid] > target){
high = mid;
}
else {
low = mid + 1;
}
}
return low;
}
- floor search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int floorSearch(int[] arr, int target){
int low = 0, high = arr.length;
while (low < high){
int mid = low + (high - low)/2;
if (arr[mid] == target){
return mid;
}
else if (arr[mid] < target){
low = mid + 1;
}
else {
high = mid;
}
}
// what if all the item in arr is bigger than target, which means low is 0
return high - 1;
}
We can know that there is a template of ceiling and floor search which is low = mid+1 and high = mid. The only difference is the return value. ceiling is the right part so we should return the low which is the mid + 1, and floor is the left part so we should return high - 1.
Second, if there are duplicates in the array, we need to be more careful about the boundary.