Most efficient way to determine in what quadrant coordinates fall

As appropriately exploited in ZuK's method, this problem is separable. I.e., you can determine the horizontal and vertical indices independently, in range 1..5 and 0..20 [step 5] respectively, and add them.

So the problem amounts to two searches among 5 intervals of unequal lengths.

This can be done with comparisons. At most 4 comparisons by sequential search, at most 3 by binary search. Less than 3 comparisons cannot be achieved unless special tricks are used that exploit symmetry. (In my opinion, not worth the effort.)

X < 100 ? 1 : X < 200 ? 2 : X < Width - 200 ? 3 : X < Width - 100 ? 4 : 5 +
Y < 100 ? 0 : Y < 200 ? 5: Y < Height - 200 ? 10 : Y < Height - 100 ? 15 : 20

Using lookup tables is a faster option if you can afford initializing these. I would not recommend using a 2D lookup table that maps the whole screen, since address computation would take one multiply anyway. Two 1D lookups are as efficient.

H[X] + V[Y]

(table H initialized with values 1, 2, 3, 4, 5 for the respective ranges, table V initialized with 0, 5, 10, 15, 20).

I don't think that using general purpose algorithms could be beneficial here given the tiny problem size.

I hope this helps,

Yves

Using arithmetic tricks, you get the not-so-efficient-as-it-might-look expression

1 +
(2 * X < Width ? Max(X / 100, 2) : 4 - Max((Width - X) / 100, 2)) +
(2 * Y < Height ? Max(Y / 100, 2) : 4 - Max((Height - Y) / 100, 2)) * 5

Quote:

---

Originally Posted by Mitsukai

no u cant... u will get invalid results. say u click, x=101 devided by 2 is 50, arr[x][y] will return x-qaudrent 0 while this qaudrants x-size is 100 but u clicked x=101 and that should be x-qaudrent 1

---

Well, in my defence - I suggested an IDEA, not implementation...
You could always add 1 before division.

faster is
(x + 2) >> 1;

Quote:

---

Originally Posted by Mitsukai

faster is
(x + 2) >> 1;

---

Two things:
1. It is NOT faster. Any good compiler will produce "sar" instruction for "/2".
2. It is NOT correct. You only need to add 1.