Clear and easy to understand binary lookup algorithm Are you sure you don't want to read it?

@

---

preamble

Please respect my original knowledge sharing and keep my blog in mind:South of the South i、

---

Tip: Below is the body of this post, with the following examples for reference

synopsis

binary search（Binary Search） It is one of the most popular methods in theFinding a specific element in an ordered arrayThe search algorithm. The search process starts in the middle of the array and ends if the middle element is exactly the element to be found; if a particular element is greater than or less than the middle element, the search is done in the half of the array that is greater than or less than the middle element, and comparisons are made from the middle element as in the beginning. If the array is empty at a given step, no element is found.

The bisection search algorithm is very efficient with a time complexity of O(log n), where n is the number of elements in the array. This is because the search range is halved after each comparison.

I. What is the principle of the binary lookup algorithm?

The principle of Binary Search Algorithm is based on the idea of partitioning, which is used to quickly find the location of a particular element in an ordered array. The core principle can be summarized in the following steps:

1. Define the scope of the search:

First, determine the starting position of the searchlow and end positionhigh, these two locations point to the first and last element of the array, respectively. In this way, the entire search range is determined.

2. Calculation of intermediate positions:

In each iteration, compute the middle of the search rangemid This is usually accomplished by placing thelow respond in singinghigh (Be careful to prevent integer overflow, it is safer to writemid = low+ ( high - low ) / 2 ）。

3. Compare intermediate elements:

Compare the element in the middle position with the target value to be found.target Make comparisons.

4. Adjustment of the scope of the search:

• If the middle element is exactly the target value to be looked up, the lookup succeeds and the index of the middle position is returned.
• If the middle element is greater than the target value, it means that the target value is in the left half of the current search range, so update HIGH tomid - 1, to narrow the search to the left half.
• If the middle element is smaller than the target value, it means that the target value is in the right half of the current search range, so update low tomid + 1, to narrow the search to the right half.

5. Repeat iterations:

Repeat steps 2 through 4, until the target value is found or the search range is empty (i.e., thelow> high ). If the search range is empty, the target value does not exist in the array, in which case you can return -1 or some other value indicating that it was not found.

The binary lookup algorithm is efficient because it halves the search range at each iteration, thus significantly reducing the number of elements to be compared. In the worst case (i.e., the target value does not exist in the array), the time complexity of the bisection lookup algorithm is O(log n), where n is the number of elements in the array. This makes bisection lookup a very useful tool when dealing with large data sets.

Note that the binary lookup algorithm requires the array to be ordered. If the array is unordered, it needs to be sorted first, but this may increase the overall time complexity. Therefore, binary lookup is typically used in scenarios where the array is already sorted or can be sorted before the lookup.

Second, what are the advantages and disadvantages of the binary lookup algorithm?

Binary Search Algorithm (BSA) as an algorithm to find a specific element in an ordered array has its own unique advantages and disadvantages. The following are the main advantages and disadvantages of Binary Search Algorithm:

Pros:

1. Efficient:
   The time complexity of the binary lookup algorithm is O(logn), where n is the number of elements in the array. This means that as the size of the array increases, the time required for the lookup grows very slowly, relative to a linear lookup (which has a time complexity of O(n)), theSignificant improvement in efficiency。
2. Wide range of applications:
   The binary lookup algorithm can be used as long as the data has been sorted. This is particularly useful in scenarios that deal with large amounts of data and require frequent lookups, such as database indexing, lookups in file systems, etc.
3. Good stability:
   The performance of the binary lookup algorithm is not affected by the initial ordering of the array (as long as it is ordered), and the time complexity of each lookup is O(log n).

Drawbacks:

1. Requires data to be in order:
   The binary lookup algorithm requires that the data must be ordered.If the data is not sorted, you need to perform a sort operation first, which may add additional computational overhead. In some cases, it may not be cost-effective to use binary lookup if sorting is expensive.

2. Only for static datasets or datasets that can be updated quickly:
   The binary lookup algorithm does not modify the original array during the lookup process, so it is particularlyFor static data setsor datasets that can be updated quickly. If the dataset changes frequently (e.g., frequent insertion or deletion of elements), it may need to be reordered or indexed after each change, which may reduce the efficiency of the binary lookup.

3. Extra space is required (in some cases):
   While the binary lookup algorithm itself does not require additional storage to hold intermediate results (since it performs the lookup directly on the original array), in some application scenarios (such as when the lookup path needs to be recorded or when multiple lookups are performed), additional data structures may be required to aid in the lookup process.

4. Memory sensitive:
   Since binary lookup relies on the random access property of arrays, its efficiency may suffer in environments where memory access is slow (e.g., when using disk as a storage medium).

In summary, the binary lookup algorithm is a very efficient lookup algorithm, but it requires that the data must be ordered, and may not be applicable to frequently changing data sets. In practical applications, it is necessary to choose whether to use the binary lookup algorithm according to the specific scenarios and needs.

Third, java implementation of binary search case

Implementing a binary lookup algorithm in Java is a common programming task. The following is an example of a simple implementation of the bisection lookup algorithm, which is used to find a specific element in an ordered array and return its index. If the element is not found, -1 is returned.

public class BinarySearch {

    /**
     * Binary search algorithm
     *
     * @param arr Ordered array
     * @param target The target value to be found.
     * @return The index of the target in the array, or -1 if not found.
     */
    public static int binarySearch(int[] arr, int target) {
        int low = 0; // define the lowest point
        int high = - 1; // Define the highest point.

        while (low <= high) {
            int mid = low + (high - low) / 2; // prevent overflow, compute the middle position
            if (arr[mid] == target) {
                // find target, return index
                return mid; } else if (arr[mid] == target) { // Find target, return index.
            } else if (arr[mid] < target) {
                // target is to the right of the midpoint, adjust the low point
                low = mid + 1; } else { // target value is to the right of the middle, adjust the low point.
            } else {
                // if the target is to the left of the center, adjust the highest point
                high = mid - 1; }
            }
        }

        // Target not found, return -1.
        return -1; }
    }

    public static void main(String[] args) {
        int[] arr = {-1, 0, 3, 5, 9, 12}; // Example array
        int target = 9; // target value to find

        int result = binarySearch(arr, target);

        if (result ! = -1) {
            ("Element " + target + " " index in the array is: " + result);
        } else {
            ("Element not found in array " + target); } else {
        }
    }
}

In this example, the binarySearch method implements the binary search algorithm. It takes an ordered array arr and a target value target as arguments and returns the index of the target value in the array. If the target is not found, -1 is returned.

In the main method, we create an example array arr and a target to find, then call the binarySearch method and print the results.

summarize

The binary lookup algorithm requires the array to be ordered. If the array is unsorted, you need to sort it first and then use the bisection lookup algorithm. In addition, the bisection lookup algorithm has a time complexity of O(log n), where n is the number of elements in the array, which makes it very efficient when dealing with large datasets. **

---

I am.South of the South iRecord the drops grow a little bit every day, learning is never ending! Reprinted with link to original article!!!