General discussions: Problem 170 (Binary search in array)

reeeeeeeee 2025-01-13 23:37:55

I have no idea what I'm doing wrong.

output from example:

10
1keei5f
bixots
1mmfpia
dwaviz
q0a5p9
l600w7
it4w75
ht85qa
1gvvigc
hg8y3f
start: 203.65.244.0 target: 203.69.1.99     offset: 203.75.255.255
start: 1kea7sw      target: 1keei5f         offset: 1keobun

start: 41.138.88.0  target: 41.138.89.240   offset: 41.138.91.255
start: bixog0       target: bixots          offset: bixp8f

start: 211.72.0.0   target: 211.72.44.226   offset: 211.79.255.255
start: 1mmfgn4      target: 1mmfpia         offset: 1mmqp6n

start: 50.22.6.0    target: 50.22.50.27     offset: 50.22.50.199
start: dwamtc       target: dwaviz          offset: dwavnr

start: 93.187.224.0 target: 93.187.227.93   offset: 93.187.227.255
start: q0a51c       target: q0a5p9          offset: q0a5tr

start: 76.73.0.0    target: 76.73.62.135    offset: 76.73.127.255
start: l5zojk       target: l600w7          offset: l60dtr

start: 67.202.65.0  target: 67.202.65.1     offset: 67.202.67.255
start: it4w74       target: it4w75          offset: it4wsf

start: 64.49.239.0  target: 64.49.240.2     offset: 64.49.240.79
start: ht85j4       target: ht85qa          offset: ht85sf

start: 190.154.0.0  target: 190.154.62.44   offset: 190.155.255.255
start: 1gvv668      target: 1gvvigc         offset: 1gvxzb3

start: 62.229.64.0  target: 62.229.82.155   offset: 62.229.95.255
start: hg8uf4       target: hg8y3f          offset: hg90qn

TW BJ TW US GB SG US US EC PT

The translated IP values are outputted when the search gets a hit. offset is start+offset

Seems to fit the ip data, but the when I run the checker it shows that I made a mistake.

zelevin 2025-01-15 15:22:23

I don't really read Rust, but to me the following lines contain an issue:

        Ordering::Less => {
            max = idx;
            idx /= 2;
        },
        Ordering::Greater => {
            min = idx;
            idx = (idx + max) / 2;
        },

reeeeeeeee 2025-01-16 02:19:53

I apologize, the code I submitted contained solutions to a few problams involving binary search, That wasn't the function I used for this problem. I used the function named search under the IPList impl.

let mut half = self.len() / 2;
    let mut step = half / 2;

    loop {
        match self.cmp(ip, half) {
            Ordering::Less => half -= step,
            Ordering::Greater => half += step,
            Ordering::Equal => return self.get_country(half),
        }
        if step == 0 {
            return "Unknown";
        }
        step /= 2;
    }

zelevin 2025-01-16 17:51:20

I don't know what's going on here, so I'd advise to write code to do a simple scan in addition to binary search and then compare the outputs.

reeeeeeeee 2025-01-17 04:28:10

Tried your suggestion, still getting the same values. I also checked manually in the ip file and my answers seem to be right. So unless the file has been changed, It seems I am missing something.

I'd be grateful if someone could validate that the file at the problem is actually correct.

gardengnome 2025-01-17 05:44:06

Hi, I do get the same output TW BJ TW US GB SG US US EC PT as you for the example based on the latest IP data file. The IP list file gets automatically updated from time to time and that of course can lead to changes/issues, see here.

reeeeeeeee 2025-01-18 07:14:27

Hi, thanks for checking. I went over my code and managed to get it to work. my binary search was poorly implmented and I didn't check for range inclusiveness on start + offset.