Time complexity of binary search technique

Binary search method, which makes full use of the order relationship between elements and adopts the divide-and-conquer strategy, can complete the search task in O(log n) in the worst case.

The basic idea is to divide n elements into two halves with roughly the same number, and take a[n/2] and the number you want to find. x is compared. If x=a[n/2], x is found and the algorithm operation terminates. (Recommended learning: web front-end video tutorial)

In computer science, binary search (English: binary search), also known as half-interval search (English: half-interval search) , Logarithmic search (English: logarithmic search) is a search algorithm for finding a specific element in an ordered array.

The search process starts from the middle element of the array. If the middle element happens to be the element to be found, the search process ends; if a specific element is greater than or less than the middle element, the search process ends when the array is greater than or less than the middle element. Search in that half, and start the comparison from the middle element as before.

If the array is empty at a certain step, it means it cannot be found. This search algorithm reduces the search range by half with each comparison.

If xa[n/2], then we only need to continue searching for x in the right half of the array a.

The binary search method is extremely widely used, and its idea is easy to understand, but writing a correct binary search algorithm is not a simple matter. The first binary search algorithm appeared as early as 1946, but the first completely correct binary search algorithm did not appear until 1962.

Bentley wrote in his book "Writing Correct Programs" that 90% of computer experts cannot write a completely correct binary search algorithm within 2 hours.

The key to the problem is to accurately formulate the boundaries of each search range and determine the termination conditions, and correctly summarize the various situations of odd and even numbers. In fact, after sorting it out, we can find that its specific algorithm is very intuitive.

Complexity calculation

Time complexity: Binary search cuts the search area in half each time. It is obvious that the time complexity is O(log n). (n represents the number of elements in the set)

Space complexity: O(1). Although defined in recursive form, it is tail recursive and can be rewritten as a loop.

The above is the detailed content of Time complexity of binary search technique. For more information, please follow other related articles on the PHP Chinese website!