6. template for integer and real number dichotomy

Integer dichotomy

1. Find... In monotonically increasing sequence x perhaps x In the subsequent

Template I ：

a[0]～a[n-1] It's monotonous 

int bin_search(int *a, int n, int x)
{
         
    int left = 0, right = n;              // Be careful ： No  n-1, At this time, it is closed on the left and open on the right [0,n)
    while (left < right) 
    {
    
        int mid = left + (right-left)/2;  //int mid = (left + right) >> 1; 
        if (x <= a[mid])  right = mid;
        else    left = mid + 1;
    }                                     // Terminate in left = right
   return left;                           // A special case ：a[n-1] < x when , return n
}

• When x <= a[mid] when , explain x stay mid Left side , The new search interval is the left half ,left unchanged , to update right = mid

• When x > a[mid] when , explain x stay mid To the right of , The new search interval is the right half ,right unchanged , to update left= mid + 1.

• After code execution ,left= right, Both equal , That is, where the answer is . The code is very efficient , Narrow the search in half at a time , The total number of times is log₂（n）.

---

2. Find... In a monotonically increasing sequence x perhaps x The precursor of

Template II ：

int bin_search2(int *a, int n, int x)
{
       //a[0]～a[n-1] It's monotonous 
    int left = 0, right = n;                
    while (left < right) 
    {
    
        int mid = left + (right-left + 1)/2 ;  
        if (x >= a[mid])  left = mid;
        else  right = mid - 1;
    }                                     // Terminate in left = right
   return left;                            
}

• When x >= a[mid] when , explain x stay mid To the right of , The new search interval is the right half , therefore right unchanged , to update left= mid;
• When x < a[mid] when , explain x stay mid Left side , The new search interval is the left half , therefore left unchanged , to update right = mid-1
• You can also analyze , When x<a[mid] when , Can not write right=mid, It can lead to while（） The death of the loop .

---

The real number is divided into two parts