3

This was asked in my interview,Here the actual meaning of the question is to find the time complexity or specifically worst case time complexity of an array of elements which are already in the sorted order.

Main point to note here is the difference between the two adjacent numbers in the array are very small or insignificant.

I approached this problem as a simple binary search which requires the array to be in sorted order and thought the Worst case time complexity is O(log n). But will this answer will change if the array elements are very close to each other as mentioned in the question.

enter image description here

What is the correct approach to solve this problem.

According to the question we can assume the array as below picture.enter image description here

Thisis defenitely not what iam asking which was shown below , because the elements are sparely differ in the difference between them and we can use binary seach.

enter image description here

Improve this question
6
  • 1
    are you asking if there is a difference between sorted array with all its elements and one with most of them? Commented Jul 31, 2016 at 12:49
  • Iam asking if the worst case can be improved in seaching when all the elements are very close to each other Commented Jul 31, 2016 at 12:51
  • 1
    Are the array elements consecutive integers in a small range like in the examples? Never strings or complex objects? Commented Jul 31, 2016 at 12:57
  • @Joni yes exactly , the difference between the integers is very less Commented Jul 31, 2016 at 12:58
  • @trincot I think the array is given sorted Commented Jul 31, 2016 at 13:00

3 Answers 3

Reset to default
1

The O(log n) binary search complexity will not change even if all the elements are equal (or "very close to each other"), as long as array is sorted. Perhaps we can improve performance by taking advantage on array values distribution and using interpolation search https://en.wikipedia.org/wiki/Interpolation_search But if implemented poorly Interpolation search could result in O(n) complexity

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

If the array shows an almost linear slope, meaning that the difference between 2 consecutive elements is almost constant across the array, you could use linear interpolation to make a guess for the index where the value could be stored:

Here is an implementation in JavaScript, but without much of specific syntax. It should be clear what is happening:

function search(arr, val) {
    var low, high, guess;
    low = 0;
    high = arr.length-1;
    while (low <= high && val >= arr[low] && val <= arr[high]) {
        // Use linear interpolation to make guess for index:
        guess = Math.round(low + (high - low) * (val - arr[low]) / (arr[high] - arr[low]));
        if (arr[guess] == val) return guess;
        console.log('Tried index ' + guess + '. No match yet for ' + val);
        if (arr[guess] < val) {
            low = guess + 1;
        } else {
            high = guess - 1;
        }
    }
    return -1; // not found
}


var arr = [1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16];
index = search(arr, 7);
console.log('Search result: index ' + index);

When the array would be perfectly linear, the algorithm will find the element on the first guess, so in O(1) time. Depending on how much deviation is present in the intervals, the time will be somewhere between O(1) and O(long n).

Improve this answer

Comments

0

In a normal binary search, each time you have to split the remaining array into 2 halves and check the right half's median, BUT if you know the elements are very close, you can add a simple check to the procedure:

instead of:

  1. check median
  2. if median is bigger: go left
  3. else if median is smaller: go right
  4. else return median
  5. repeat

you can modify 2 & 3 into: go right/left by abs(median - searched_number) this should shorten your average case time complexity, but not sure how to measure it

Improve this answer

1 Comment

and what if we are searching "1" in an array of 2-s : [2, 2, 2, 2, 2, 2, 2]. I think the complexity would be linear in this case for your algorithm. so this is worse than classic binary search

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.