NVIDIA

www.nvidia.com

Interview Question

Systems Software Engineer Interview(Student Candidate) Pune (India)

Binary Search, Insertion Sort,

Answer

Interview Answer

1 Answer

0

#include <stdio.h>

unsigned int round_up(unsigned int size) {
    return ( (size & 0x1) ? ((size >> 1) + 1) : (size >> 1) );
}

unsigned int round_down(unsigned int size) {
    return ( size >> 1 );
}

int binary_search(unsigned int key, unsigned int* array ,unsigned int size) {

        if (!array || size < 1)
            return -1;

        if (size == 1)
            return (*array == key);

        return ( binary_search(key, array, round_down(size)) || binary_search(key, array+round_down(size), round_up(size)) );
}

int main(int argc,char* argv[]) {

    unsigned int array[] = {1,3,9,10,17,21};

    if (binary_search(atoi(argv[1]),array, sizeof(array)/sizeof(*array) ))
        printf("Find it!\n");
    else
        printf("Didn't find it!\n");

    return 0;
}

The Dude on Jun 8, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.