For example, consider the sorted array 2, 3, 4, 8, 10, 11. A shift of 3 places to the right would be denoted by i=2 and the shifted array would look like this: 10, 11, 2, 3, 4, 8,

For i=-2, the shifted array would look like: 4, 8, 10, 11, 2, 3.

Write code to find if a given number is present in this array.

Solution: The brute force method to search all elements in the array would yield an O(n) solution, so obviously that's not the best approach. We are not leveraging the sorted nature of the array in this case.

Now, how can we leverage the sorted nature of the array? Let assume that 'i' was 0. In that case the array would be sorted and not shifted at all (0 shift). Whats the fastest way to search in a sorted array? Binary Search! We can split the array in 2 halves and do a recursive search in one of the halves until we find the number we are looking for ( or not, if its not in the array ). This approach has a running time of O(log n), which is obviously better than n.

But, the fact that the array is shifted by 'i' number of elements complicates things a little bit. Now, instead of splitting the array in equal halves, we split the array at the shift index and do a recursive binary search. There are issues we need to tackle when the shift is greater than the length of the array or if the shift is negative. I guess the code below will make much more sense than my description of the solution.

Code: We will assume that we are provided with a method below that does binary search for us and won't bother implementing it here.

// myArray is the input array // startIndex and endIndex are the indexes in the // array where the binary search starts and ends // The method returns the index of the searchVal // if found in the array, else it returns -1 int BinarySearch(int[] myArray, int startIndex, int endIndex, int searchVal); // this method will return the index of the searchVal // if found, else it return -1 int SearchElement(int[] myArray, int shift, int searchVal) { // to take care of scenarios where the shift is more // than the length of the array shift = shift % myArray.Length; // -ve shift can be seen as positive shift equal to // the length of the array - ( -ve shift) if (shift < 0) shift = myArray.Length + shift; if(myArray[shift] <= searchVal && myArray[myArray.Length - 1] >= searchVal) { return BinarySearch(myArray, shift, myArray.Length - 1, searchVal); } else if(myArray[0] <= searchVal && myArray[shift - 1] >= searchVal) { return BinarySearch(myArray, 0, shift-1, searchVal); } return -1; }

Hi, I did it slightly differently via a regular binary search with an additional "shift" argument:

ReplyDeleteThe code: http://goo.gl/6JcAw

The test: http://goo.gl/9Gv3f

Also, one can extend this exercise and ask to find a shift. One way to do so could be like this:

ReplyDelete* Compare first and last array's elements.

* If first is less than the last then there's no shift, do a regular binary search.

* If first is greater than the last then there is a shift.

* Start doing kind of binary search looking for element where previous to it is not less, but greater than the element itself. That's the "11 - 2" breaking point in the examples.

* Element's index is a shift. Do a binary search with shift (my previous comment).

Two binary searches and we're still with logN solution. Plus, I'd compare all elements met along the way with an element searched originally - we can stumble upon it accidentally.