CSDN daily practice -- half search of ordered table

Problem description ：

When using an ordered table to represent a static lookup table , Generally, the search function can be implemented by half search .

The search process of half search is ： First, determine the scope of the records to be checked , Then gradually narrow the scope until the corresponding record is found or determined not to be found . And the scope to be reduced each time is half of that of the last time , Such a search process can be called a half search .

The second line contains n Positive integers separated by spaces , Express n An ordered integer . Input guarantees this n An integer is incremented from small to large .

The third line contains k Positive integers separated by spaces , Express k The target of this query .

Output ：

Only 1 That's ok , contain k It's an integer , Each query result is represented separately . If the corresponding integer is found in the query , Then output its corresponding position , Otherwise output -1.

Please output a space after each integer , And notice that the output at the end of the line wraps .

The following program realizes this function , Please fill in the blanks ：

#include <stdio.h>
int binary(int* a, int key, int n)
{
    int left = 0, right = n - 1, mid = 0;// For the first time left=0,n=19
    mid = (left + right) / 2;// The first two points 
    while (left < right && a[mid] != key)
    {
        if (a[mid] > key)// When the target value is to the left of the median , Let the sequence number before the median at this time be the sequence number of the right value 
        {
            right = mid - 1;
        }
        else if (a[mid] < key)// When the target value is to the right of the median , Let the sequence number of the last digit of the median at this time be the sequence number of the lvalue 
        {
            left= mid +1;
        }
        mid = (right + left) / 2;// Calculate the median for the second time , Can be cycled all the time 
    }
    if (a[mid] == key)
        return mid;
    return -1;
}
int main(void)
{
    int Base_a[20] = { 1, 3, 5, 8, 9, 40, 120, 123, 125, 150, 199, 200, 1250, 1255, 1900, 2000, 2001, 3000, 3950, 5000 };
    int Search_a[5] = { 12, 199, 9, 2001, 3500 };
    int result = 0x00;
    for (int i = 0; i < sizeof(Search_a) / sizeof(Search_a[0]); i++)//sizeof(Search_a) / sizeof(Search_a[0]) Get the length of the array to be queried 
    {
        result = binary(Base_a, Search_a[i], sizeof(Base_a) / sizeof(Base_a[0]));// Get the length of the entire group of numbers to be indexed , by 20,n=19
        printf("[%d %d] ", Search_a[i], result);// Output [ Target element , Element subscript ],result Yes -1 and mid Two value taking methods 
    }
    printf("\n");
    return 0;
}

 

 

  explain ： I feel this is consistent with the principle of dichotomy , There may be some mistakes in my notes , If found , Please point out , If it helps you , Please give me a compliment ！