Article directory
- 1. What is the binary search algorithm?
-
- 1.1 Introduction
- 1.2 Implementation ideas
- 2. Example of binary search
- 3.Arrays.binarySearch() in jdk
- 4. Analysis of the core binary search method in jdk
-
- 4.1 Why low is the insertion point
- 4.2 Why negation is necessary: – (low + 1)
- 4.3 Why not directly return the opposite number of the insertion point low, but also need to perform the + 1 operation
- 4.4 Can + 1 be changed to -1?
- 5. When the target element is not found, the array is expanded based on the return value.
1. What is the binary search algorithm
1.1 Introduction
Binary search algorithm, also known as Half search algorithm, is a search algorithm for finding a specific element in ordered array.
1.2 Implementation ideas
- In the initial state, the entire sequence is used as the search area.
- Find the intermediate element in the search area and compare it with the target element.
- If they are equal, the search is successful;
- If the middle element is larger than the target element, it means that the target element is to the left of the middle element, and the left area is used as the new search area;
- On the contrary, if the middle element is smaller than the target element, it means that the target element is located on the right side of the middle element, and the right area is used as the new search area;
- Repeat step two until the target element is found. If the search area cannot be narrowed any further and does not contain any elements, it means that there is no target element in the entire sequence and the search fails.
2. Example of binary search
/**
* Binary search (ascending array version)
*
* @param array ascending array to be searched
* @param targetValue The target value to be found
* @return If found, the index of the target value is returned. If not found, -1 is returned.
*/
public static int binarySearch(int[] array, int targetValue) {<!-- -->
// left border
int left = 0;
//right border
int right = array.length - 1;
int mid;
while (left <= right) {<!-- -->
/*
Considering that the value of left + right may exceed the maximum value that can be represented by int, we no longer divide their sum directly by 2
We know that the operation of dividing by 2 can be replaced by the bit operation >>1
But it’s not enough. Since the overflow of (left + right) value indicates a negative number, >>1 just performs the operation of dividing by 2. The highest sign bit remains unchanged. It is still 1 to indicate a negative number. A negative number divided by 2 is still a negative number.
At this time, we can modify it to unsigned right shift >>>1, the low bit overflows, and the high bit is filled with 0. Then the highest sign bit is 0, which means a positive number.
*/
mid = (left + right) >>> 1;
if (targetValue < array[mid]) {<!-- -->
// If the target value of the search is smaller than the middle index value, narrow the right boundary of the search
right = mid - 1;
} else if (array[mid] < targetValue) {<!-- -->
// If the middle index value is less than the target value of the search, narrow the left boundary of the search
left = mid + 1;
} else {<!-- -->
// If found, return the target index
return mid;
}
}
// Exit the while loop, indicating that if it is not found, -1 is returned to indicate that it is not found.
return -1;
}
Arrays.binarySearch() in 3.jdk
public class Arrays {<!-- -->
public static int binarySearch(int[] a, int key) {<!-- -->
return binarySearch0(a, 0, a.length, key);
}
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {<!-- -->
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {<!-- -->
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
}
With the binary search example just now, the implementation of the binary search method in jdk is almost the same, except that the return value is different from our example. When the target value is not found in the array:
- Our example will return -1 as an indication that the element is not found;
- In jdk, the variant of the target value to be inserted into the point is used as the identifier of the element that cannot be found. This means that we can do more with this return value, such as expanding the array based on the point to be inserted when the target value does not exist, and adding the target value to the array.
Regarding the return value when the target value cannot be found in jdk, we give an example to help better understand what is Variation of the insertion point of the target value:
-
Given the array [2, 5, 8], the target value to be found is 4;
-
Obviously, 4 does not exist in the array, so the return value of the binary search algorithm in jdk is
-2, then according tothe return value = -(insertion point + 1)It can be deduced that the insertion point should be1, which is the position where the array index is 1; -
That is, if the unfound target value 4 needs to be inserted into the array, it should be placed at index 1, that is, after the element
2with index 0.Index 0 1 2 3 Original array 2 5 8 New array 2 4 5 8
Analysis of the core binary search method in 4.jdk
/**
* Use the binary search algorithm to search for the specified value in the specified integer array. The array must be sorted (by method sort(int[]) ) before making this call.
* If unsorted, the result is undefined. If an array contains multiple elements with a specified value, there is no guarantee which element will be found.
* Parameters:
* a – the array to search
* key – the value to search for
* Returns: the index of the search key (if it is contained in the array); otherwise returns - (insertion point + 1).
* The insertion point is defined as the point at which a key is inserted into the array: the index of the first element is greater than the key, or a.length if all elements in the array are less than the specified key.
* Note that this guarantees that the return value will be >= 0 if and only if the key is found.
*/
public static int binarySearch(int[] a, int key) {<!-- -->
return binarySearch0(a, 0, a.length, key);
}
// Like public version, but without range checks.
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {<!-- -->
// left border
int low = fromIndex;
//right border
int high = toIndex - 1;
while (low <= high) {<!-- -->
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
// Return -(insertion point + 1)
return -(low + 1); // key not found.
}
We need to think about two questions now:
- Why low is the insertion point
- Why negation is necessary:
-(low + 1) - Why not just return the opposite number of the insertion point low? You also need to perform the + 1 operation
- Can +1 be changed to -1?
4.1 Why low is the insertion point
Assuming that the target result cannot be found, there are a few things we need to understand:
- As the number of cycles increases, the distance between low and high will become closer and closer. Until just entering the last round of loop, it must be
low == high. - When the target is not found in the end, the while loop is exited, there will be low > high, and
low = high + 1
//When the last round enters the loop, low == high
while (low <= high) {<!-- -->
// Then mid == high == low
int mid = (low + high) >>> 1;
int midVal = a[mid];
/*
Either go into if or go into else if
1. When the intermediate value is smaller than the target value, it means that the target value to be inserted should be one position behind the intermediate value index mid.
That is, low = mid + 1, so low is the insertion point
\t\t
2. When the target value is less than the middle value, it means that the target value to be inserted should be one position before the middle value index mid.
Since we want to place it in front of mid, doesn't it mean that we have to occupy the position of mid and move the elements after mid one position backward?
So the insertion point is the current position of mid, and low is equal to mid, so it is equivalent to low, which is the insertion point.
*/
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
4.2 Why negation is necessary: -(low + 1)
We use a positive number to identify the index of the target value found in the array.
Because low + 1 must be a positive number. Therefore, we can only negate the negative number to indicate that the target value has not been found, and then reverse the variation to obtain the insertion point.
4.3 Why not directly return the opposite number of the insertion point low, but also need to perform the + 1 operation
For example, for the array [2, 5, 8], we need to find the index with the target value of -6, then it will definitely not be found. The low obtained at the end of the loop is 0, that is, the target value needs to be inserted at the index of -6 0 position.
If the returned value is not -(low + 1) but -low, that is -0. In Java, 0 == -0 is true and therefore is considered to be the target value found at index 0.
4.4 Can + 1 be changed to -1?
No, the result of low + 1 must be a positive number, but is the result of low – 1 guaranteed to be a positive number? It is not possible. For example, when the low point to be inserted is 1, the final result returned is -(low - 1), which is 0. Then it will be considered that the target value is found and the index is 0, which is unreasonable.
5. Expand the array based on the return value when the target element is not found
public static void main(String[] args) {<!-- -->
//Binary search target value, insert if it does not exist
/*
Original array: [2,5,8]
Find target value: 4
The query cannot be found, and the returned result is r = -index of the point to be inserted-1
Here the insertion point index is 1, which corresponds to r = -2
Then we divide it into these steps to copy:
- 1. Create a new array with the size of the original array + 1: [0,0,0,0]
- 2. Put the data before the index of the insertion point into a new array: [2,0,0,0]
- 3. Place the target value at the index of the point to be inserted: [2,4,0,0]
- 4. Copy all the data at the end of the original array to the end of the new array: [2,4,5,8]
*/
//Define the original array and target value
int[] oldArray = {<!-- -->2, 5, 8};
int target = 4;
//Search target value 4, not found, the return result is r = -index of the point to be inserted-1, here r=-2
int r = Arrays.binarySearch(oldArray, target);
// r < 0 means the target value is not found, so insert it
if (r < 0) {<!-- -->
// r = -(insertion point + 1) => insertion point = -r - 1
// Get the index to be inserted
int insertIndex = -r - 1;
// 1. Create a new array with the size of the original array + 1
int[] newArray = new int[oldArray.length + 1];
// 2. Put the data before the index of the insertion point into the new array
// The new array consists of [0,0,0,0] --> [2,0,0,0]
for (int i = 0; i <= insertIndex - 1; i + + ) {<!-- -->
newArray[i] = oldArray[i];
}
// 3. Place the target value at the index of the point to be inserted
// The new array consists of [2,0,0,0] --> [2,4,0,0]
newArray[insertIndex] = target;
// 4. Copy all the data behind the original array to the new array one after another
// The new array consists of [2,4,0,0] --> [2,4,5,8]
for (int i = insertIndex; i <= oldArray.length - 1; i + + ) {<!-- -->
newArray[i + 1] = oldArray[i];
}
System.out.println(Arrays.toString(newArray)); // [2, 4, 5, 8]
}
}
Of course, the copying methods in the second and fourth steps are actually similar. We can encapsulate a public method myArraycopy ourselves to call:
public static void main(String[] args) {<!-- -->
//Binary search target value, insert if it does not exist
/*
Original array: [2,5,8]
Find target value: 4
The query cannot be found, and the returned result is r = -index of the point to be inserted-1
Here the insertion point index is 1, which corresponds to r = -2
Then we divide it into these steps to copy:
- 1. Create a new array with the size of the original array + 1: [0,0,0,0]
- 2. Put the data before the index of the insertion point into a new array: [2,0,0,0]
- 3. Place the target value at the index of the point to be inserted: [2,4,0,0]
- 4. Copy all the data at the end of the original array to the end of the new array: [2,4,5,8]
*/
//Define the original array and target value
int[] oldArray = {<!-- -->2, 5, 8};
int target = 4;
// Search target value 4, not found, the return result is r = - index of the point to be inserted -1, here r = -2
int r = Arrays.binarySearch(oldArray, target);
// r < 0 means the target value is not found, so insert it
if (r < 0) {<!-- -->
// r = -(insertion point + 1) => insertion point = -r - 1
// Get the index to be inserted
int insertIndex = -r - 1;
// 1. Create a new array with the size of the original array + 1
int[] newArray = new int[oldArray.length + 1];
// 2. Put the data before the index of the insertion point into the new array
// The new array consists of [0,0,0,0] --> [2,0,0,0]
myArraycopy(oldArray, 0, newArray, 0, insertIndex);
// 3. Place the target value at the index of the point to be inserted
// The new array consists of [2,0,0,0] --> [2,4,0,0]
newArray[insertIndex] = target;
// 4. Copy all the data behind the original array to the new array one after another
// The new array consists of [2,4,0,0] --> [2,4,5,8]
myArraycopy(oldArray, insertIndex, newArray, insertIndex + 1, oldArray.length - insertIndex);
System.out.println(Arrays.toString(newArray));
}
}
/**
* Copy array elements
*
* @param oldArray old array
* @param oldArrayStartCopyIndex The position where the old array elements start copying
* @param newArray new array
* @param newArrayStartCopyIndex The position where the new array element starts to be copied
* @param copyLength length of copied elements (number)
*/
public static void myArraycopy(int[] oldArray,
int oldArrayStartCopyIndex,
int[] newArray,
int newArrayStartCopyIndex,
int copyLength) {<!-- -->
for (int i = 0; i < copyLength; i + + ) {<!-- -->
newArray[newArrayStartCopyIndex + + ] = oldArray[oldArrayStartCopyIndex + + ];
}
}
But of course, in fact, jdk has provided us with the method System.arraycopy for copying array elements. The function of this method provided by jdk and our customized myArrayCopy method parameters and effects are the same, so we can completely modify the copy method to System.arraycopy:
public static void main(String[] args) {<!-- -->
//Binary search target value, insert if it does not exist
/*
Original array: [2,5,8]
Find target value: 4
The query cannot be found, and the returned result is r = -index of the point to be inserted-1
Here the insertion point index is 1, which corresponds to r = -2
Then we divide it into these steps to copy:
- 1. Create a new array with the size of the original array + 1: [0,0,0,0]
- 2. Put the data before the index of the insertion point into a new array: [2,0,0,0]
- 3. Place the target value at the index of the point to be inserted: [2,4,0,0]
- 4. Copy all the data at the end of the original array to the end of the new array: [2,4,5,8]
*/
//Define the original array and target value
int[] oldArray = {<!-- -->2, 5, 8};
int target = 4;
// Search target value 4, not found, the return result is r = - index of the point to be inserted -1, here r = -2
int r = Arrays.binarySearch(oldArray, target);
// r < 0 means the target value is not found, so insert it
if (r < 0) {<!-- -->
// r = -(insertion point + 1) => insertion point = -r - 1
// Get the index to be inserted
int insertIndex = -r - 1;
// 1. Create a new array with the size of the original array + 1
int[] newArray = new int[oldArray.length + 1];
// 2. Put the data before the index of the insertion point into the new array
// The new array consists of [0,0,0,0] --> [2,0,0,0]
System.arraycopy(oldArray, 0, newArray, 0, insertIndex);
// 3. Place the target value at the index of the point to be inserted
// The new array consists of [2,0,0,0] --> [2,4,0,0]
newArray[insertIndex] = target;
// 4. Copy all the data behind the original array to the new array one after another
// The new array consists of [2,4,0,0] --> [2,4,5,8]
System.arraycopy(oldArray, insertIndex, newArray, insertIndex + 1, oldArray.length - insertIndex);
System.out.println(Arrays.toString(newArray));
}
}