Binary search method

introduction .

The premise of the topic is that the array is an ordered array , At the same time, the title also emphasizes There are no duplicate elements in the array , Because once there's a repeating element , The element subscript returned by binary search method may not be unique , These are the prerequisites for using dichotomy , When you see that the Title Description meets the above conditions , But think about whether you can use dichotomy . Binary search involves many boundary conditions , The logic is simple , But I just can't write well . For example, what is it  while(left < right)  still  while(left <= right), What is the right = middle Well , Still right = middle - 1 Well ？ People often write dichotomy in disorder , Mainly because The definition of interval is not clear , The definition of interval is invariant . In the process of binary search , Keep invariants , Is in the while Every boundary treatment in the search must adhere to the operation according to the definition of interval , This is it. Loop invariants The rules .

One . Determine the interval — Left and right closed or Left closed right away

      Adhere to loop invariants , Keep the interval rules consistent

Two . Analysis of the specific situation

        1. Left closed right closed binary search

left=0
right=len(nums)-1

while (left <= right):
    middle = (left + right) //2 
    
    if (nums[middle] > target):
        right=middle-1

    elif (nums[middle] < target):
        left=middle+1
    
    else:
        return middle

return -1

        2. Left close right open binary search  

left=0
right=len(nums)-1

while (left < right):
    middle = (left + right) //2
    
    if (nums[middle] > target):
        right=middle
    
    elif (nums[middle] < target):
        left=middle+1

    else:
        return middle

return -1

         3. Left open right close binary search  

left=0
right=len(nums)-1

while (left < right):
    middle = (left + right) //2
    
    if (nums[middle] > target):
        right=middle-1
    
    elif (nums[middle] < target):
        left=middle

    else:
        return middle

return -1

         4. Open left and right to find  

left=0
right=len(nums)-1

while (left <= right):
    middle = (left + right) //2
    
    if (nums[middle] > target):
        right=middle
    
    elif (nums[middle] < target):
        left=middle

    else:
        return middle

return -1

  3、 ... and . summary

        Whatever form of binary search , The overall structure of the code is the same ; The difference lies in the opening and closing of the interval boundary

left=0
right=len(nums)-1

while (left <=/< right): #  When the boundary can take the same value <=; Otherwise, it would be <
    middle = (left + right) //2
    
    if (nums[middle] > target):
        right=middle/middle-1 #  Open interval is middle, The closed interval is middle-1
    
    elif (nums[middle] < target):
        left=middle/middle+1 #  Open interval is middle, The closed interval is middle+1

    else:
        return middle

return -1

Four .Leetcode Title Reference

34. Find the first and last positions of the elements in the sort array

35. Search insert location

69. x The square root of  

367. Effective complete square number

704. Two points search