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).


     
Second attempt for the Cracking coding interview question.

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

Here is a solution in python.


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)