#include<iostream> bool is_in_array(int* begin, int* end, int target){ int mid = (end - begin)/2; if(*begin>target || *end<target) //value has to be between [begin,end] return false; // to continue if(begin[mid] == target) return true; if(begin[mid] > target) //look at the left subarray return is_in_array(begin,begin+mid-1,target); // (begin[mid] < target) look at the right subarray return is_in_array(begin+mid+1,end,target); } bool find_in_array(int arr[] ,int target,int size){ int* begin = arr; int* end = begin+size-1; bool result = is_in_array(begin,end,target); return result; } void test_is_in_array(bool expected, int arr[],int target,int size){ bool result = find_in_array(arr,target,size); std::cout<<(result==expected?"PASS: ":"FAIL: ") <<" result => "<<result<<" expected =>" <<expected<<std::endl; } int main( void ){ int arr1[] = {1,3,5,7,9,10}; int arr2[] = {1,3,7,9,10}; int arr3[] = {1,3,5,7,9,10,11,15,16,16,16,16,16,19,20}; int arr4[] = {1,3,5,7,9,10,15,20,25,50,1000,1000001}; int arr5[] = {1,3,5,7,9,10,11,12,13,14}; test_is_in_array(0,arr1,0,sizeof(arr1)/sizeof(*arr1)); test_is_in_array(1,arr2,7,sizeof(arr2)/sizeof(*arr2)); test_is_in_array(1,arr3,16,sizeof(arr3)/sizeof(*arr3)); test_is_in_array(1,arr4,50,sizeof(arr4)/sizeof(*arr4)); test_is_in_array(0,arr5,15,sizeof(arr5)/sizeof(*arr5)); test_is_in_array(1,arr5,14,sizeof(arr5)/sizeof(*arr5)); return 0; }
Given an input string, write a regular recursive function that returns the decoded (uncompresseed form) Run Length Encoded (is a simple form of data compression where repeated character are replaced by count followed by the character repeated) string for the input string. Below are some examples: decode("*") =>* decode("3+") =>+++ decode("11*") =>*********** decode("101+") =>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ decode("abcde10+10*10+10x") =>abcde++++++++++**********++++++++++xxxxxxxxxx decode("\\") =>\ decode("\1\2\3") =>123 decode("13\7x") =>7777777777777x decode("5\\") =>\\\\\ decode("4\12\23\3") =>111122333 decode("4\\2\3") =>\\\\33 NOTE: To represent a single backslash, it’s necessary to place double backslashes (\\) in the input string to obtain the desired in
Comments
Post a Comment