Searching an element in a sorted array and in rotated sorted arrays

Anyone knows any use cases of rotated sorted array. Please add comments.

Sorted array search

Searching an element in a sorted array can be done using binary search. It can be implemented in recursive or non-recursive methods.

Here the logic is:

· Compute middle index to divide the array into sub arrays

· Check if the element pointing to middle index is matching with key value

· If matching, done, goal achieved 😊

· If not matching, we have to decide if we need to search in first sub-array or second sub-array:

· This decision is easier here as it is sorted array assuming that elements sorted in ascending order.

· If key value is lesser to middle-element , repeat above steps with first sub-array, else repeat above steps with second sub-array

· We need to stop this search either with matching element or if no more elements in sub-array

Rotated Sorted array search

Rotated sorted array is a sorted array where some of the elements are shifted back.

eg. [6,7,8,0, 2,3,5], [45,47,3,12,25,35,37,44]

Searching in a rotated sorted array is a bit tricky 😊 with O(log n) time. We can take the approach similar to the above with some modifications:

· Compute middle index to divide the array into sub arrays

· Check if the element pointing to middle index is matching with key value

· If matching, done, goal achieved 😊

· If not matching, we have to decide if we need to search first sub-array or second sub-array. These sub-arrays can be sorted arrays or one sub-array can be sorted array and another sub-array can be rotated sorted array.

· In case of sorted sub-array follow the sorted array approach

· In case of rotated sub-arrays, to check if key falls under first-sub array by checking key value with array of low-index ( key >= arr[low-index]) or key value will be less than middle element of array.

· In case if array contains duplicates above logic may work or may not work. If it does not work, then complete traversal of array is must.