Searching number in the circular array [reviewed]

Problem

Given the circular array of sorted values, search the specified value.

For example, A = { 4,5,6, 1,2,3}, target = 1; output  = true

Your algorithm should be better than O(N).



In general, searching the sorted array for the number can be easily done by using binary search in O(log n).

We can leverage that idea to solve this "circular array problem" with minor tweaks.

Let's examine the possible edge cases:

Say the signature will be like below:

bool binary_search( int * input, int start, int end, int target)

1. given start and end position calculate the half.

2. check if the input[half] is equal to a target. If so, we found it !. return true;

3. if input [half] is not equal to a target value. examine the two cases.

Case 1. if input[half] < target :

In this case, we ought to look for the right half of the array in the normal array according to the     binary search. However, we additionally check if input[end] >= target in the circular array.

Examine the following case:
   
  Given array: {4,5,6,7,1,2,3}, your "half" was 1 and target is 5.  This falls into Case 1.
  If we blindly search the right half of the array starting from "2" and ending with "3".

  Our algorithm will return false. In the case above, we are supposed to search the left half of the array instead. That's why we need "input[end] >= target" before deciding whether to choose left half or right half.

Case 2. if input[half] > target:

 Same as Case 1, we should choose the left half of the array in normal case. However, we should make sure, input[start] <= target before making final decision.

  I would not illustrate why this time. Think for yourself.

Now, we can write the code based on the algorithm we wrote.

14:57 min : to write up the code.

Running time: O( log N).

	#include <iostream>
	using namespace std;
	bool search_list(int* list, int s, int e, int target)
	{
	if (s > e)
	return false;
	int h = s + (e-s)/2;
	if (target == list[h])
	return true;
	if (target < list[h])
	{
	if (target >= list[s])
	e = h-1;
	else
	s = h +1;
	} else {
	if (target <= list[e])
	s = h+1;
	else
	e = h-1;
	}
	return search_list(list, s, e, target);
	}
	int main ()
	{
	int input[8] = {4,5,6,7,8,1,2,3};
	cout<<" finding 3 = "<<search_list(input, 0, 7, 3)<<endl;
	cout<<" finding 5 = "<<search_list(input, 0, 7, 5)<<endl;
	cout<<" finding 9 = "<<search_list(input, 0, 7, 9)<<endl;
	return 1;
	}

view raw circular_binary_search.cpp hosted with ❤ by GitHub

     
Second attempt for the Cracking coding interview question.

	#include<vector>
	#include<iostream>
	using namespace std;
	int search(vector<int>& A, int s, int e, int t)
	{
	if (s>e)
	return INT_MIN;
	int h = s + (e-s)/2;
	if ( A[h] == t)
	return h;
	else if ( A[h] > t )
	{
	if ( A[s] > t )
	s = h+1;
	else
	e = h-1;
	} else {
	if (A[e] < t)
	e = h-1;
	else
	s = h +1;
	}
	return search(A, s, e, t);
	}
	int find_in_circular_array(vector<int>& A, int target)
	{
	return search(A, 0, A.size()-1, target);
	}
	int main()
	{
	int arr[12] = {15,16,19,20,25, 1, 3, 4,5,7,10,14};
	vector<int> input(arr, arr + 12 );
	for(int i = 0; i < input.size(); i++)
	cout<<input[i]<<",";
	cout<<endl;
	int result = find_in_circular_array(input, 25);
	cout <<" pos of 25: "<< result<<endl;
	return 1;
	}

view raw find_num_in_circular_array.cpp hosted with ❤ by GitHub

UPDATE(2019-07-31): solved the problem again in python.

Here is a solution in python.

	def circular_binary_search(list, s, e, target):
	if s > e:
	return False
	half = s + (e - s)//2
	if list[half] == target:
	return True
	elif list[half] > target:
	#check if we can still search left side.
	if list[s] > target:
	#search right side
	return circular_binary_search(list, half + 1, e, target)
	return circular_binary_search(list, s, half - 1, target)
	else:
	#check if we can still search right side.
	if list[e] < target:
	#search left side instead
	return circular_binary_search(list, s, half - 1, target)
	#search right side as planned
	return circular_binary_search(list, half + 1, e, target)
	input = [4,5,6, 1,2,3]
	target = 1
	print ("input = {} target = {} output = {}".format(input, target, circular_binary_search(input, 0, len(input)-1, target)))
	input = [4,5,6, 1,2,3]
	target = 4
	print ("input = {} target = {} output = {}".format(input, target, circular_binary_search(input, 0, len(input)-1, target)))
	input = [4,5,6, 1,2,3]
	target = 7
	print ("input = {} target = {} output = {}".format(input, target, circular_binary_search(input, 0, len(input)-1, target)))

view raw facebook_circular_binary_search.py hosted with ❤ by GitHub

Practice statistics:

07:38: come up with a complete algorithm
09:00: to write up the code with two bugs (one with extra ':' in return statement, the other in test code)