Binary Search | Data Structure and Algorithm
Binary search is a famous question in algorithm. For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity. If the target number does not exist in the array, return -1. Example If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2. Challenge If the count of numbers is bigger than MAXINT, can your code work properly?
Overflow: mid = start + (end - start) / 2; when write this code, extract as a method first.
注意数组中可能有重复值,
https://shanzi.gitbooks.io/algorithm-notes/content/problem_solutions/implement_valid_binary_search.html
Given a sorted array and a target, find the element just greater than the target. If does not exist, return array[0].
http://massivealgorithms.blogspot.com/2015/01/beating-binary-search-algorithm.html
Read full article from Binary Search | Data Structure and Algorithm
Binary search is a famous question in algorithm. For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity. If the target number does not exist in the array, return -1. Example If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2. Challenge If the count of numbers is bigger than MAXINT, can your code work properly?
Overflow: mid = start + (end - start) / 2; when write this code, extract as a method first.
注意数组中可能有重复值,
https://shanzi.gitbooks.io/algorithm-notes/content/problem_solutions/implement_valid_binary_search.html
- Your code should handle array with zero and one elements.
- To calculate the mid point,
left + ((right - left) >> 1)is better than(left + right) / 2as it won't exceed range ofintvalue. - Take care of boundary changes to avoid infinite looping.
public int search(int[] array, int target) {
if (array.length == 0) return -1;
int l = 0;
int r = array.length - 1;
int mid;
while (l <= r) { // we are using l <= r here so that array with only one elements will be handled
mid = l + ((r - l) >> 1); // get mid with out (l + r) so that it won't exceed range
if (array[mid] == target) return mid;
else if (array[mid] < target) {
l = mid + 1;
} else {
r = mid - 1; // minus one here to avoid infinite looping.
}
}
return -1;
} public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) { // maybe also check start, end value, exit early?
return -1;
}
int start = 0;
int end = nums.length - 1;
int mid;
while (start + 1 < end) { // may change to start<=end, so no need check start,end value after loop
mid = start + (end - start) / 2; // avoid overflow when (end + start)
if (target < nums[mid]) {
end = mid;
} else if (target > nums[mid]) {
start = mid;
} else {
end = mid;
}
}
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}Given a sorted array and a target, find the element just greater than the target. If does not exist, return array[0].
Understand the problem:
The problem asks for finding the next element greater to the target. So it suggests a binary search solution. e.g.
1 2 3 4 5, and target is 3, we return 4.
There are several corner cases to consider:
1. What if the last element i.e. A[n - 1] is equal or less than the target, then we return A[0].
2. What if it contains duplicates. In this case, we cannot just return the next element of the target, e.g.
1 2 3 3 4, and target = 3. In this case, we will first find the first 3. If we simply returns the next element of 3, it would be errorly 3, not 4. So we might linearly search the rest of the element if it is equal to the target until a greater one, but the algorithm will degrade to a O(n) solution at the worst case.
1 2 3 4 5, and target is 3, we return 4.
There are several corner cases to consider:
1. What if the last element i.e. A[n - 1] is equal or less than the target, then we return A[0].
2. What if it contains duplicates. In this case, we cannot just return the next element of the target, e.g.
1 2 3 3 4, and target = 3. In this case, we will first find the first 3. If we simply returns the next element of 3, it would be errorly 3, not 4. So we might linearly search the rest of the element if it is equal to the target until a greater one, but the algorithm will degrade to a O(n) solution at the worst case.
public static int searchForGreater(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int len = nums.length; if (target >= len) { //? return nums[0]; } int lo = 0; int hi = len - 1; while (lo + 1 < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] == target) { lo = mid + 1; } else if (nums[mid] > target) { hi = mid; } else if (nums[mid] < target) { lo = mid + 1; } } if (nums[lo] > target) { return nums[lo]; } else if (nums[hi] > target) { return nums[hi]; } return nums[0]; }Read full article from Binary Search | Data Structure and Algorithm
