Searching Algorithm (搜索专项讨论)

[YuezhenQin]

Searching Algorithm

LinearSearch

BinarySearch: searching for an element's index or insertion point if it doesn't exist.

SegmentTree

[YuezhenQin]

Binary Search

If you have a sorted array arr and an element x, then in O(logn) time and O(1) space, binary search can:

1. find the index of x, if it is in arr
2. find the first or the last index in which x can be inserted to maintain being sorted otherwise

Here's the idea behind binary search: We can discard the half that can't contain x, and then repeat the process on the other half. We continue this process of cutting the array in half until we find x.

public int binarySearch(int[] arr, int target) {
    /* define the current search space */
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; /* halve the search space at every iteration */
        if (arr[mid] == target) return mid;
        if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left; /* left is at the insertion point */
}

In the Java and C++ implementations (with integer sum overflow), instead of doing (left + right) / 2, we do left + (right - left) / 2 to avoid overflow.

[YuezhenQin]

If your input has duplicates, you can modify the binary search template to find either the first or the last position of a given element.

Find the left-most index	Find the right-most index + 1 (insertion point)

Regarding both of the above templates, if the element you are searching for does not exist, then left will be at the index where the element should be inserted to maintain sorted order