Thanks a lot,
So, apparently it is possible to use a re bytes pattern to search through array.array('u') and it works as well for numpy.chararray.
However, I suppose that for doing this you need to have knowledge of the internal encoding, because re.search will actually compare bytes (from the pattern) to unicode chars (from the array). So, the bytes have to be utf32-encoded strings, I suppose.
Currently I have not enough knowledge of how Python strings are implemented. I'm convinced that it's a good thing to have mutable strings, but I guess it could indeed be hard to implement.