Semi sorted binary search

Question

Say you have an array that is "semi-sorted", e.g. something like this:

[7,8,9,10,1,2,3,4,5,6]

Where a part of the end of the sorted array was transferred to the beginning.

Is there a way to still find an element in it in log(n) time?

Here's my solution:

def findVal(arr, val):
    return helper(arr, 0, len(arr) - 1, val)

def helper(arr, start, end, val):
    if (start > end) :
        return False  # empty array

    mid = start + (end - start) // 2

    if (arr[mid] == val):
        return True

    if (mid == 0):
        return False  # 1 element array which is not the value

    rightSorted = arr[mid] <= arr[end]

    if (rightSorted):
        if (val > arr[mid] and val <= arr[end]):
            return helper(arr, mid + 1, end, val)
        else:
            return helper(arr, start, mid - 1, val)

    else:
        if (val < arr[mid] and val >= arr[start]):
            return helper(arr, start, mid - 1, val)
        else:
            return helper(arr, mid + 1, end, val)

I guess you could also do this with a simple while loop instead of recursion.

Answer 1

The solution seems to be very specific to having exactly two parts of the list interchanged.

I'd be more tempted to write something more general, for when there might be many such sorted subsections.

• Make a single pass through the list and initialize a table that records each segment's starting and ending indexes (or start index and length).
• Sort that table based on the value at the starting index.

Then, to perform a search:

• Binary search the table to determine the appropriate section.
• Binary search the section of the list.

Note that if the table ends up being huge, this approach isn't appropriate.

---

If one always knew for sure that the original list was always in only two parts, it might seem that it would be faster and easier to write very specific code.

But if the general algorithm is applied to that simple case, in practice it does almost no more work than the ad hoc method.

Specific problems are often best solved by general solutions.

In the real world, next week, next month, or next year, your teacher, your boss, or your client will eventually say, "That program was great. Can you change it to handle three sections of sorted data?". The original special purpose approach will take considerable work to change (and even if it isn't a lot, realized that eventually you'll be asked for four sections). The general approach will be trivial (update the documentation), but you don't need to let your boss or client know that.

Answer 2

I spend some more time refining the solutions. Also found a relevant question that asks to find the min/max of the array here.

Problem Context

Searching a value in an array can be up to O(n) in time complexity - you have to iterate through the array and check for each element if it's equal the search value. But - if the array is sorted, this is reduced to O(log(n)) due to a strategy called Binary Search. Binary search allows us at each time cut half of the options to consider. You check the middle element in the array, if the search value is bigger you can discard the lower half, if it's lower you can discard the upper half, and now you do the same for the remaining array - until you either find the value or end up with an empty/1-element array - in that case the element is not in the array.

Here there is a problem that the array is swapped - the question is can we still reduce the time complexity to O(log(n)) ?

The key insight here is that even though the array itself is not perfectly sorted, at least half of it IS - and so we can always tell something about that half, and reduce our scope. This is true for every sub-division we make of the array - at least half of it will be sorted (and in some cases, both halves).

If we are looking for the min/max value, we basically don't care about the part that is sorted, because the pivot value will be in the other half (though the mid value should be included, as it can be the min/max value) - so we can discard the sorted part.

If we are looking for a specific value - we can automatically check if our value is in the range of the sorted half, if it is we discard the non-sorted half, and focus on the sorted. If it's not we focus on the non-sorted - and do the same.

Find Min value

Here is a solution in python - here we check if the right half is sorted. If it is, we reduce our scope to the left half. If not, we reduce our scope to the right half (note that in that case we can safely discard the mid point and move beyond it).

def findMin(arr):
    start = 0
    end = len(arr) - 1
    while(start < end):
        mid = (start + end) // 2
        rightSorted = arr[mid] < arr[end]
        if rightSorted:
            end = mid
        else:
            start = mid + 1
    return arr[start]

The decision to check the right is not arbitrary - it is necessary in case we search for a min value. If we instead search the left, and find out it is sorted - we could not confidently discard that half, as the array might be perfectly sorted - in that case the 0th element is the minimum. So we choose the right in order to be completely sure we still have the min value in the sub array.

Find Max value

In python this is actually very easy - you just need to go one element before the minimum - and even if the min is in 0 position, python interprets -1 as the last element of the array. So you could just use the same code as above, but with return arr[start-1].

Alternatively, we could reverse the min function above:

def findMax(arr):
    start = 0
    end = len(arr) - 1
    while(start < end):
        mid = (start + end) // 2
        leftSorted = arr[mid] > arr[start]
        if leftSorted:
            start = mid
        else:
            end = mid - 1
    return arr[start]

Finding a specific value

If we want to check if a specific value exists in the array - the same key insight hold.

def findVal(arr, val):  
    start = 0
    end = len(arr) - 1    
    while(start < end):
        mid = (start + end) // 2
        leftSorted = arr[start] <= arr[mid]
        if leftSorted:
            if val >= arr[start] and val <= arr[mid]:
                end = mid
            else:
                start = mid + 1
        else:
            if val >= arr[mid] and val <= arr[end]:
                start = mid
            else:
                end = mid - 1
    return val == arr[start]

A few differences:

1. we have to check if our value is in the sorted half, and if not discard it.

2. we have to watch out for the case of 2 elements in an ordered array. The issue here is that if we are not careful, we can end up in an endless loop - because the mid point will be either the 1st or the 2nd, depending if we are using a floor or a ceil operation. Since the default python // operation is a floor, mid will be equal to start, and we have to check the left side in order to either choose the 1st or discard it. [if we use ceil, we should check the right side]