Binary search

The premise condition

When the collection of the target we need to search is an ordered array, we can optimize the filtering times through binary search to reduce the search time

Implementation Process (C language)

• We do it recursively
• Declare functions

// Binary search returns the subscript of the target
int binary_search(int target, int *src, int start, int end);
Copy the code

• Define a function

// Implement the incrementing set (PS: decrement set, step 3 and step 4 swap)
int binary_search(int target, int *src, int start, int end) {
    / / step 1
    if (start > end) {
        // Boundary problem, target does not exist
        return - 1;
    }
    // Compromise the subscript
    const int index = (start + end) >> 1;
    / / step 2
    if (src[index] == target) {
        // Find the target and return the subscript
        return index;
    }
    if (src[index] > target) {
        / / step 3
        // The target is smaller than the element, recursively looking for the left interval
        // PS: index-1, boundary problem, remove already filtered current element
        return binary_search(target, src, 0, index - 1);
    }
    / / step 4
    // The target is larger than the element
    // PS: index + 1, boundary problem, remove already filtered current element
    return binary_search(target, src, index + 1, end);
}
Copy the code

• test

int main(a) {
    int list[10] = {0.1.2.3.4.5.6.7.8.9};
    printf("index: %d\n", binary_search(2.list.0.9));
    return 0;
}

// result index: 2
Copy the code

summary

Binary search for small details, boundary processing compromise will omit the screening elements, do a good job of boundary processing