This article shares with you the variant of Java implementing binary search for reference. The specific content is as follows
Normal binary search:
First review the ordinary binary search
Note: There is a problem with binary search: when there are duplications in the array, such as {3, 3, 3, 3}, when binary search 3, the return is arr[1], which means binary search will not return the position 0 of the first occurrence of 3.
public class BinarySearch { public static <T extends Comparable<? super T>> int search(T arr[], T value) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = (left & right) + ((left ^ right) >> 1); if (arr[mid].compareTo(value) == 0) { return mid; } else if (arr[mid].compareTo(value) > 0) { right = mid - 1; } else { left = mid + 1; } } return -1; } public static void main(String[] args) { Integer[] arr = new Integer[]{1, 3, 3, 6, 7, 9}; //-1 System.out.println(search(arr, 0)); //0 System.out.println(search(arr, 1)); //5 System.out.println(search(arr, 9)); //-1 System.out.println(search(arr, 10)); //2 System.out.println(search(arr, 3)); }}Bipartite variant: findFirst function
In normal binary search, search in the [left......right] left-closed and right-closed interval. If an element with a value is found, it is considered to be found. This is not the case in this findFirst function. In the [left......right] left-closed right-closed interval, when the element with a value equals value is found, instead of right = mid - 1, let right = mid, continue to search in the [left......right] left-closed right-closed interval. The loop exits when left== right finally exits.
After exiting the loop, the value may be found, or it may be that the loop does not find the value after traversing the complete array, and exits the loop.
So after exiting the loop, you have to judge which situation is.
public class BinarySearch { public static <T extends Comparable<? super T>> int findFirst(T arr[], T value) { int left = 0; int right = arr.length - 1; //Exit when left>=right, the "=" situation here is different from binary while (left < right) { int mid = (left + right) >> 1; if (arr[mid].compareTo(value) < 0) { left = mid + 1; } else { right = mid; } } // After the above loop is traversed. Has the value been found? Still no value was found? Just make a judgment. if (arr[left] == value) { return left; } else { return -1; } } public static void main(String[] args) { Integer[] arr = new Integer[]{1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 6, 7, 9}; //-1 System.out.println(findFirst(arr, 0)); //0 System.out.println(findFirst(arr, 1)); //12 System.out.println(findFirst(arr, 9)); //-1 System.out.println(findFirst(arr, 10)); //1 System.out.println(findFirst(arr, 3)); }}Bipartite variant: fewer function
introduce
Given an array and a variable value, find the number from the array that is closest to the value value and smaller than the value. For example arr = {11, 22, 22, 33, 33, 33, 44, 54} value = 33. 22 is closest to value, and smaller than value.
So the answer is 2 (22 in the lower corner marker in the array arr).
If no number smaller than value is found, then output -1.
Solution
Use binary search method. Each time, use arr[mid] to compare with the value. Small, equal, go to the left to look for it; big, go to the right to look for it. You may not understand the "equal" situation in the previous sentence. Ordinary binary search is to find arr[mid] == value, while the fewer function is to find a number smaller than value, so although arr[mid] == value, you have to continue to look for a smaller value on the left.
example
Code
public class BinarySearch { public static <T extends Comparable<? super T>> int fewer(T arr[], T value) { int left = 0; int right = arr.length - 1; //Exit while when left > right (left <= right) { int mid = (left & right) + ((left ^ right) >> 1); if (value.compareTo(arr[mid]) <= 0) { right = mid - 1; } else { left = mid + 1; } } return right; } public static void main(String[] args) { Integer[] arrF = new Integer[]{21, 23, 25, 25, 31, 34, 37, 39, 52, 63}; //3 System.out.println(fewer(arrF, 30)); }}Bipartite variant: greater function
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.