The witch is found in the dark swamp, which is unlocked (I think) by doing the Lost Acolyte quest for Othra (the lizard priestess).
