A Brain Teaser

News & General Discussion
1

I had a brain teaser put to me today. You have a sorted array of say 950000 ints of which there are… let’s just posit a number…900120 indexes. Devise a function that uses the fewest iterations possible to find the index of the value passed in. I came up with one solution but it occurred to me that I could possibly do it with less and came up with this. It is somewhat of a hack…but often my best work is. I am not a compsci grad…Just an artist and lover of brain teasers and puzzles who learned how to code by the seat of his pants.

void FindIndexFast (int value, int[] array) {
    int ones = value % 10;
    int tens = value % 100;
    int hundreds = value % 1000;
    int thousands = value % 10000;
    int tenThousands = value % 100000;
    int hundredThousands = value % 1000000;
    int idx;
    //assumes sorted array is over 900000 ints
    for (int i = array.Length; i > 0; i - 1000) {
        //go backwards by 1000 indexes at at a time
        //when below the number you have the starting index for next  loop
        if (array[i] % 1000000 < hundredThousands) {
            idx = i;
            break;
            //max iterations is 900
        }
    }
    for (i = idx; i < array.Length-idx; i + 100) {
        //go forwards from index gotten in first loop by 100 at a time
        //when equal you have found the range
        if (array[i] % 100000 == tenThousands) {
            //just in case you missed an int that was at the very next index of previous loop
            idx = i - 99;            
            break;
            //max iterations is 100?
        }
    }
    for (i = idx; i < array.Length-idx; i + 10) {
        //go forwards from index gotten in previous loop by 10 at a time
        //when equal youhave found the range
        if (array[i] % 10000 == thousands) {
            //just in case you missed an int that was at the very next index of previous loop
            idx = i - 9;            
            break;
        }
    }
    for (i = idx; i < array.Length-idx; i + 10) {
        //go forwards from index gotten in previous loop by 10 at a time
        //when equal youhave found the range
        if (array[i] % 1000 == hundreds) {
            //just in case you missed an int that was at the very next index of previous loop
            idx = i - 9;            
            break;
        }
    }
    for (i = idx; i < array.Length-idx; i++) {
        //when equal youhave found the range
        if (array[i] % 100 == tens) {
            idx = i;            
            break;
        }
    }
    for (i = idx; i < array.Length-idx; i++) {
        //when equal youhave found the range
        if (array[i] % 10 == ones) {
            idx = i;            
            break;
        }
    }
    return idx;
}

The final idx is the index of the value. I ran this through my head only but it seems that it would be a few thousand iterations at most and if yer lucky as few as 8 or 9. Does anybody here have a better solution that may take less iterations? Put yer thinking caps on.

2

Not sure I understand the question… If the array is sorted then use Binary Search. It’s O(log n).

2 Likes
3

By simply looking at the middle index each time, (ie a binary search), you could get the index in a sorted array of this size in just 20 iterations. That’s pretty quick.

If you make some assumptions about the distribution of the data going in, you can go even faster. (At the cost of going slower if your assumptions are wrong).

1 Like
4

Explain to me a binary search. How does one approach this and can you post a code snippet… Like I said … I am an artist that learned how to code mostly in the art domain…character rigging and controllers, UI, arrays of objects etc…

5

Let’s say your friend parked 10 cars in the parking lot and sorted them by odometer. Then he tell you to find the car that has 62400 miles.

Since you know they are sorted, the trick is that you can go straight to car number 5 and check the odometer. If you find out the number is less than 62400 you can be sure to ignore all cars on the first half. Using the same trick, you can now go straight to car number 8. Let’s say this time the odometer is higher than 62400. Well, now you know you don’t need to check cars 9 or 10 because they will be even higher…

Each iteration your search scope is divided by half thus the logarithmic curve. That’s as fast as you can search on a sorted array - assuming no other conclusion can be made about the data.

Computer science folks call this ‘divide and conquer’.

Hope my parking lot example makes sense :S

6

Not overly optimised, or even tested, it’s probably got an infinite loop in it somewhere. But you get the idea.

void FindIndexFast (int value, int[] array) {
    int highIndex = array.Length - 1;
    int lowIndex = 0;
    while (highIndex != lowIndex){
        index = (highIndex - lowIndex)/2);
        if (array[index] > value) {
            lowIndex = index;
        } else {
            highIndex = index;
        }
    }
    return lowIndex;
}
7

Here is the version I came up with when i realized in a flash what you folks meant…is this correct… I did it slightly different.

void FastIndexFinder (int[] array, int value) {
        //find the value at the middle index
        int high = array.Length;
        int mid = array.Length/2;
        int low = 0;
        while (low < mid) {
            //compare the value to the mid point index array value
            if (array[mid] < value) {
                low = mid + 1;//add one so that you can have a spread
                //until it gets to a point where high equals low and then you have the answer
            } else {
                high = mid;
            }
        }
        if (low == high && array[low] == value) {
            return low;
        }
    }
8

Yes… Thanks… Another cool code trick to add to my schtick… Never had to iterate through more than a few hundred items prior.

9

Shouldn’t the void be an int?

10

This is the ticket. Thanks for your input and output:)… edit : But why is Length blue on one line and purple on the next?

int BinaryIndexFinder (int[] array, int value) {
        //find the value at the middle index
        int idx = 0;
        int high = array.Length-1;
        int mid = array.Length/2;
        int low = 0;
        while (low < mid) {
            mid = (high - low)/2;
            //compare the value to the mid point index array value
            if (array[idx] < value) {
                low = mid + 1;//add one so that you can have a spread
                //until it gets to a point where high equals low and then you have the answer
            } else {
                high = mid;
            }
        }
        if (low == high && array[low] == value) {
            idx = low;
            return idx;
        } else {
            return -1;//not found
        }
     
    }
11

Yeah, writing code on the phone has never been the best idea.

12

Nor writing code over skype for a job test:)