As a qualified programmer, the importance of mastering basic common algorithms is self-evident; As a simple and efficient search algorithm, binary search is very important to master its usage.Copy the code
  • 1. What is binary search?
    • Binary search is an efficient search algorithm, which realizes efficient search by the way of half-fold comparison. The premise of binary search is in a linear list of ordered sequences.
  • 2. Binary search process
    • Search steps:
    1. Calculates the index in the middle of the sequence, and compares the target value with the corresponding value of the indexCopy the code
    2. If the target value is equal to the index value, return the index valueCopy the code
    3. If the index value is less than the target value, it indicates that the target value is to the right of the index value, and search on the rightCopy the code
    4. If the index value is greater than the target value, it indicates that the target value is to the left of the index value, and search on the leftCopy the code
  • 3. Binary search JAVA implementation code 
    /** * @author Ming * @date 2021/8/2 14:05 */ public class BinarySearch {/** ** Public static void Main (String[] args) {int[] num = new int[]{1,3,5,6,7,9,10}; int findResult = 5; System.out.println(findAndReturnResult(num,findResult)); } static Integer findAndReturnResult(int[] num, int findResult){ //1. // The left pointer defaults to the index of the first element in the array; Int left = 0,right = num.length - 1; // intermediate variable int TMP; While (left <= right){//3. Determine the middle position of comparison; TMP = left + (right-left) / 2; TMP = left + (right-left) / 2; if(num[tmp] == findResult){ return tmp; } // If the value to be compared is larger than the target value, narrow the range of the right pointer so that right = tmp-1; if(num[tmp]>findResult){ right = tmp - 1; } left = TMP + 1; left = TMP + 1; left = TMP + 1; else{ left = tmp + 1; } } return null; }}Copy the code
  • 4. The graphical process of binary search
    • Below is the num array in the code

    • According to the code algorithm processing logic, first initialize the left pointer and the right pointer;

    • Calculates the intermediate index value and compares the value corresponding to the index with the target value

    • Follow the rules:
    1. If the target value is equal to the index value, return the index valueCopy the code
    2. If the index value is less than the target value, it indicates that the target value is to the right of the index value, and search on the rightCopy the code
    3. If the index value is greater than the target value, it indicates that the target value is to the left of the index value, and search on the leftCopy the code

    • Num [2] == 5 (num[2] == 5);

    Ps:

    • 1. Loop if the left pointer is less than or equal to the right pointer
    • 2. The time complexity of binary search algorithm is O(log2n)
  • 5. The application of binary search in life
    • Binary search algorithm may be used by criminals to fraud, of course, apes learn binary search, will not be fooled.