myEsn2E9

[Binary search] is an efficient search algorithm based on the divide and conquer strategy. It utilizes the ordered nature of the data to reduce the search range by half each time, until the target element is found or the search range is empty.

First, initialize the pointers i=0 and j=n-1, pointing to the first and last elements of the array, representing the search range [0, n-1]. The square brackets indicate a closed interval, which includes the boundary values themselves.

Next, perform the following two steps in a loop:

1. Calculate the midpoint index $m = \lfloor {(i + j) / 2} \rfloor$, where $\lfloor : \rfloor$ represents the floor operation.
2. Compare nums[m] and target, and consider the following three cases:
   1. If nums[m] < target, it means target is in the range [m+1, j], so set i=m+1.
   2. If nums[m] > target, it means target is in the range [i, m-1], so set j=m-1.
   3. If nums[m] = target, it means the target is found, so return the index m.

If the array does not contain the target element, the search range will eventually shrink to empty. In this case, return -1.

It is worth noting that since i and j are of type int, i+j may exceed the range of the int type. To avoid integer overflow, the formula $m = \lfloor {i + (j - i) / 2} \rfloor$ is commonly used to calculate the midpoint.

/* Binary Search (closed interval) */
int BinarySearch(int[] nums, int target) {
    // Initialize the closed interval [0, n-1], where i and j point to the first and last elements of the array
    int i = 0, j = nums.Length - 1;
    // Loop until the search range is empty (when i > j)
    while (i <= j) {
        int m = i + (j - i) / 2;   // Calculate the midpoint index m
        if (nums[m] < target)      // This case indicates that the target is in the range [m+1, j]
            i = m + 1;
        else if (nums[m] > target) // This case indicates that the target is in the range [i, m-1]
            j = m - 1;
        else                       // The target element is found, return its index
            return m;
    }
    // The target element is not found, return -1
    return -1;
}

Advantages: It has good performance in terms of time and space.

Limitations:

• It is only suitable for ordered data. If the input data is unordered, it is not worth sorting the data specifically for binary search.
• It is only suitable for arrays (contiguous storage space).
• For small data sets, linear search performs better. In algorithm problems, linear search is often replaced by hash search to reduce the time complexity of the algorithm.
  • Linear search: trading time for space
  • Hash search: trading space for time

Binary search insertion point: Binary search can not only be used to search for target elements, but also has many variations, such as searching for the insertion position of a target element.

Binary search boundaries:

1. Finding the left boundary
2. Finding the right boundary

Linear search is suitable for small or frequently updated data;

Binary search is suitable for large, sorted data;

Hash search is suitable for data that requires high query efficiency and does not require range queries;

Tree search is suitable for large dynamic data that needs to maintain order and support range queries.

References#

• Chapter 10   Searching - Hello Algorithm (hello-algo.com)