Simple understanding of binary search

Detailed description

The search process of binary search starts from the middle element of the array , If the middle element is exactly the element to find , Then the search process is over ; If a particular element is greater than or less than the middle element , Find in the half of the array that is larger or smaller than the middle element , And it's the same as the beginning, starting from the middle element . If the array is empty at a certain step , You can't find . This search algorithm reduces the search range by half every time it is compared .

The detailed implementation steps of binary search are as follows ：

1. In an ordered list , Take the intermediate record as the comparison object ;
2. If the given value is equal to the key of the intermediate record , Then the search is successful ;
3. If the given value is less than the keyword of the intermediate record , Then continue to search in the left half of the middle record ;
4. If the given value is greater than the keyword of the intermediate record , Then continue to search in the right half of the middle record ;
5. Repeat the steps 1~4, Until the search is successful , Or all search areas have no records , Until the search fails .

Algorithm diagram

Problem solving

What are the limitations of binary search algorithm ？

Binary search algorithm requires random access according to subscripts . So it is more suitable for array structure , It is not suitable for linked list structure , The time complexity of random access to data by an array according to the subscript is \(O(1)\), The time complexity of random access of linked list is \(O(n)\).

Binary search is for ordinal numbers . Binary search can only be used to insert 、 Delete operations are not frequent , In a scenario where you sort multiple times , For dynamically changing data sets , Binary search will no longer work .

The amount of data is too small for binary search . In a size of 10 Find an element in the array of , Whether it's binary search or sequential traversal , The search speed is almost the same , Only when there is a large amount of data , The advantage of binary search is obvious .

Too much data is not suitable for binary search . Binary search is used on the data structure of array , It's hard to store too large data in an array , You can't use binary search .

What are the variations of binary search algorithm ？

• Find the first element whose value is equal to the given value
• Find the last element whose value is equal to the given value
• Find the first element greater than or equal to the given value
• Find the last element less than or equal to the given value

Code implementation

Find interface

package cn.fatedeity.algorithm.search;

public interface Search {
    int search(int[] numbers, int target);
}

Binary search class

package cn.fatedeity.algorithm.search;

/**
 *  Binary search class 
 */
public class BinarySearch implements Search {
    private int search(int[] numbers, int target, int left, int right) {
        if (left > right) {
            return -1;
        } else if (left == right) {
            if (numbers[left] == target) {
                return left;
            } else {
                return -1;
            }
        }
        if (target < numbers[left] || target > numbers[right]) {
            return -1;
        }

        int mid = (left + right) >> 1;
        if (numbers[mid] > target) {
            return this.search(numbers, target, left, mid - 1);
        } else if (numbers[mid] < target) {
            return this.search(numbers, target, mid + 1, right);
        } else {
            return mid;
        }
    }

    @Override
    public int search(int[] numbers, int target) {
        return this.search(numbers, target, 0, numbers.length - 1);
    }
}