月度归档： 2022 年 1 月

Exercise 3.1 Our binary search makes two tests inside the loop, when one would suffice (at the price of more tests outside). Write a version with only one test inside the loop and measure the difference in run-time.

Original for loop code:

/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] */
int binsearch(int x, int v[], int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid])
            high = mid + 1;
        else if (x > v[mid])
            low = mid + 1;
        else /* found match */
            return mid;
    }
    return -1; /* no match */
}

Modified code:

#include<stdio.h>

int binsearch(int x, int v[], int n);

main() {
    int arr[] = { 1,3,5,7,8,10,22,24,26,28,41,43,45,47,50,51 };
    printf("%d", binsearch(7,arr,10));
}

int binsearch(int x, int v[], int n) {
    int low, high, mid;

    low = 0;
    high = n - 1;

    mid = (low + high) / 2;

    while (low < high && x != v[mid]) {
        if (x > v[mid]){
            low = mid + 1;
        } else {
            high = mid - 1;
        }
        mid = (low + high) / 2;
    }
    if (x == v[mid]){
        return mid;
    } else {
        return -1;
    }
}

Exercise 3.2 Write a function escape(s,t) that converts characters like newline and tab into visible escape sequences like \n and \t as it copies the string t to s . Use a switch . Write a function for the other direction as well, converting escape sequences into the real characters.