search for an item in a sorted array that has been rotated.

rotated.d

import std.stdio;

auto search(int[] array, int target)
{
	int low = 0;
	int high = array.length-1;
	debug writeln("target = ", target);
	while (low <= high) {
		debug writefln("low=%d, high=%d", low, high);
		auto mid = (low + high + 1) / 2;
		debug writeln("array[mid] = ", array[mid]);
		if (array[mid] == target) {
			return mid;
		} else if (array[low] < array[mid]) {
			if (target < array[mid] && target >= array[low]) {
				high = mid-1;
			} else {
				low = mid + 1;
			}
		} else {
			if (target > array[mid] && target <= array[high]) {
				low = mid + 1;
			} else {
				high = mid-1;
			}
		}
	}
	return -1;
}

auto contains(int[] array, int target)
{
	return search(array, target) != -1;
}

void main()
{
	auto array = [7,11,14,-1,0,1,3,5,5,6];

	assert(contains(array, -1,));
	assert(contains(array, 3,));
	assert(!contains(array, 4,));
	assert(contains(array, 5,));
	assert(contains(array, 7,));
	assert(contains(array, 14,));
	assert(!contains(array, 12,));
}