CareerCup

Linear search, complexity O(N). Is the array sorted, except the spaces? If, yes binary search, and at each step check if you found a space, in which case move one position to the left, or to the right.

@zammer: what does element refer here?Does it mean character?

What is unique about this problem? just matching one character at a time and stopping when match is found is simple solution but doesn't it sound too simple?

I agree with Sumit

This array should be sorted, not characters array, but strings array.
The solution can be found sites.google.com/site/spaceofjameschen/home/sort-and-search/find-string-in-a-sorted-array-interspersing-with-spaces

Please Explain Question With an example .

The question would make more sense if it is sorted and requires better than O(n), for O(n) it's too simple

If the array is sorted, then may be binary search is fine

public static int findIndex(char[] A, char ch){

int low=0;
int high=A.lengh()-1;

while(low<=high)
{
int mid=(high-low)/2 -low;

if(A[mid]==ch){
return mid;}

else if (A[mid]<ch)
{
low=mid+1;
while(A[low]==' '){
low++;
}
}

else 
{
high=mid-1;
while(A[high]==' '){
high--;
}
}

}
return -1;

}

Using Binary Search

int chSearch(string& str,char val, int start, int end, bool shift = true)
{

	if(start == end)
		return -1;
	if(str[start]==val)
		return start;
	if(str[end]==val)
		return end;
	int mid = (start+end)/2;
	if(shift)
	{
		while (str[mid]== ' ')
		{
			mid --;
		}
	}
	else
	{
		while (str[mid]== ' ')
		{
			mid ++;
		}
	}
	if(str[mid]==val)
		return mid;
	if(str[mid]<val)
		chSearch(str,val,mid,end,false);
	else
		chSearch(str,val,start,mid);
}
int binarySearch(string &str,char val)
{
	int length = str.length();
	if(val < str[0] || val > str[length-1])
		return -1;
	return chSearch(str,val,0,length-1);
}