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.<\/p>\n\n\n\n
Original for loop code:<\/p>\n\n\n\n
\/* binsearch: find x in v[0] <= v[1] <= ... <= v[n-1] *\/\nint binsearch(int x, int v[], int n)\n{\n int low, high, mid;\n low = 0;\n high = n - 1;\n while (low <= high) {\n mid = (low + high) \/ 2;\n if (x < v[mid])\n high = mid + 1;\n else if (x > v[mid])\n low = mid + 1;\n else \/* found match *\/\n return mid;\n }\n return -1; \/* no match *\/\n}<\/code><\/pre>\n\n\n\nModified code:<\/p>\n\n\n\n
#include<stdio.h>\n\nint binsearch(int x, int v[], int n);\n\nmain() {\n int arr[] = { 1,3,5,7,8,10,22,24,26,28,41,43,45,47,50,51 };\n printf(\"%d\", binsearch(7,arr,10));\n}\n\nint binsearch(int x, int v[], int n) {\n int low, high, mid;\n\n low = 0;\n high = n - 1;\n\n mid = (low + high) \/ 2;\n\n while (low < high && x != v[mid]) {\n if (x > v[mid]){\n low = mid + 1;\n } else {\n high = mid - 1;\n }\n mid = (low + high) \/ 2;\n }\n if (x == v[mid]){\n return mid;\n } else {\n return -1;\n }\n}<\/code><\/pre>\n\n\n\nExercise 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.<\/p>\n\n\n\n
<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"