Binary Search is a highly efficient Search method. Binary search is usually used to find the best solution to a problem in an interview or algorithm contest. Dichotomous search is often used to examine the coding ability and algorithmic thinking of the interviewer.

Binary search is also called split search. If a search problem can eliminate half of the search area with a condition, the target is searched in a specific space, reducing the search space. Although the idea of binary search is more intuitive, most interviewees usually do not consider the boundary processing fully, and thus make mistakes.

There are many reasons why binary lookup processing boundaries fail! For example, when the target is at the 0th index of the array, or at the (n-1) index, the program goes into an infinite loop.

Next, this question will analyze binary search algorithm from scratch, summarize a set of Python binary search code template, and analyze algorithm complexity!

1. Algorithm template

The following code is a standard implementation of binary lookup:

left = 0
right = size of array       The size of the array

while (left + 1 < right)
  mid = (left + right) / 2          # middle mid subscript

  if (array[mid] == target)         # Check found
    return mid
  else if (array[mid] < target)  
    continue search in right side   # Search in the right range
  else  
    continue search in left side    # Search the left range

if (array[left] == target)          # Judge after loop exits
  return left

return -1
Copy the code

Analyze the above pseudocodes one by one:

  • Line 1:0 as the left left index.

  • Line 2: Array size as right index. Therefore, be careful when accessing the right index.

  • Line 4: The while loop ends when there are no elements between left and right. Therefore, notice that if there is only one element in the array, the loop is skipped and 14 lines of code are required to process.

  • Line 14: Check the element on the left index outside the loop because it might be the numeric target to look for when the loop exits.

2. Coding implementation

Here is the complete binary lookup code:

def binarySearch(nums, target) :
  if len(nums) == 0:
    return -1

  The left index starts at 0
  left = 0
  The initial value of the right index is the number of elements in the array
  right = len(nums)
  # left + 1 >= right completes the while loop
  while left + 1 < right:
    mid = (right + left) // 2;

    if nums[mid] == target:
      # mid is the index of the target
      return mid
    elif nums[mid] < target:
      Searching in the left half of the array makes no sense
      left = mid
    else:
      Searching in the right half of the array makes no sense
      right = mid
  # left can be the index of the target
  if nums[left] == target:
    return left
  Target does not exist in array
  return -1

def main() :
  nums = [1.3.5.7.11.13.17.19.23.29.31.37.41.43.47.53.59];

  print("Index of 37 is ---> " + str(binarySearch(nums, 37)))
  print("Index of 1 is ---> " + str(binarySearch(nums, 1)))
  print("Index of 59 is ---> " + str(binarySearch(nums, 59)))
  print("Index of 25 is ---> " + str(binarySearch(nums, 25)))

main()
Copy the code

To find37For example, animation:

Edge cases

Now, consider whether the algorithm can handle boundary cases correctly:

  • The target is the first element in the array:

  • The target is the last element in the array:

  • Target does not exist in array:

3. Core details

Binary search problems, though, get bogged down in thinking about specific situations. However, most binary lookup problems rely on the same core concepts. If you use the same approach, you can easily bypass all the specific problems.

The binary search algorithm in this question is built on the following key points:

  • Left points to index 0.

  • Rigth is the array size (note not the index of the last element of the array).

  • Loop condition left + 1 > right.

  • Moves left or right to the midpoint mid index.

  • Check for a match on the left index outside the loop.

4. The complexity of the

Time complexity

The basic feature of binary search is to reduce the search area to half of the original space at a time.

Let’s say we have n elements in our current search space, and every iteration, we decrease by n/2 elements. The search area continues to be halved, from n to (n/2), to (n/4), to (n/8), and so on, until the area becomes 1 (unless you found the target in one of the previous steps and quit).

Finally, either find the target value or prove that it does not exist in the search space. So the total running time is how many steps you can take (divide n by 2 each time) until n becomes 1. Here’s a visual representation of the algorithm in the worst case:

  • When the target is the first element of the array:

  • When the target is the last element of the array:

The array in the example above has
17 17 An element. In order to find the target value, we have to keep halving to get an element, and the total number of iterations is a logarithmic function
l o g 2   17 = 4 log_2\space 17=4 . Therefore, at most
4 4 One iteration is enough to reduce the array to one element. if
n n It’s the total number, and it’s going through
l o g 2   n log_2 \space n You can find the answer in half, in time
O ( l o g 2   n ) O(log_2 \space n) .

Spatial complexity

Binary search occupies very little space, and its core is several variables such as left, right and mid, so its space complexity is O(1).

5. Section

This article introduces in detail the binary search principle and its coding implementation, combined with a large number of animation demonstration, I hope to help you. But binary search algorithm thinking is very widely used, in the interview or Leetcode there are a lot of binary deformation problems, such as seeking peaks, troughs, rotation array and so on.

If you want to know more about the binary algorithm and its deformation related problems, you can see the binary search algorithm class, through 12 lectures on the binary problem and related strengthening deformation problems were comprehensively analyzed.

Pythontip, Happy Coding!