Algorithm (4th Edition) - Binary Search

Start using CSDN to record the learning process today, first make up the content you have seen before.

基础概念

First, assume that the elements in the table are sorted in ascending order, compare the keywords recorded in the middle position of the table with the search keywords. If the two are equal, the search is successful; otherwise, the intermediate position record will be used. The table is divided into two sub-tables. If the keyword recorded in the intermediate position is larger than the search keyword, the previous sub-table is further searched, otherwise the next sub-table is further searched. Repeat the above process until you find a record that meets the criteria, making the search successful, or until the child table does not exist, and the search is unsuccessful.

——Baidu Encyclopedia

Code Implementation

Algorithm (Fourth Edition) The binary search uses recursive implementation, I use iterative implementation here.

用案例测试结果

/**
* Binary search method
*/
Public class BinarySearch {
/**
* @param nums is looking for an array
* @param target is looking for an integer
* @return returns the index of the found number, if it is not found, returns -1.
*/
Public static int search(int[] nums, int target) {
Int N = nums.length;
Int first = 0; //start of array
Int last = N - 1; //Array endpoint
Int mid = (first + last) / 2;
While (first < last) {

If (target > nums[mid]) {
First = mid + 1;
Mid = (first + last) / 2;
} else if (target < nums[mid]) {
Last = mid;
Mid = (first + last) / 2;
} else {
Return mid;
}
}
Return -1;
}
Public static void main(String[] args) {
Int[] nums = {0,3,45,89,132};
Int target = 89;
Int re = search(nums, target);

If (re > -1) {
System.out.println("Found" + re);
} else {
System.out.println("Not found");
}
}
}

总结

二分找, also known as Binary Search, is a more efficient method of finding. However, a binary search requires that the linear table must have a sequential storage structure, and the elements in the table are ordered by keyword. Its time complexity is O(log2N) and the space complexity is O(1).