Searching a number in a rotated sorted Array

by

The solution still works out to a binary search in the sense that you’ll need to partition the array into two parts to be examined.

In a sorted array, you just look at each part and determine whether the element lives in the first part (let’s call this A) or the second part (B). Since, by the definition of a sorted array, partitions A and B will be sorted, this requires no more than some simple comparisons of the partition bounds and your search key.

In a rotated sorted array, only one of A and B can be guaranteed to be sorted. If the element lies within a part which is sorted, then the solution is simple: just perform the search as if you were doing a normal binary search. If, however, you must search an unsorted part, then just recursively call your search function on the non-sorted part.

This ends up giving on a time complexity of O(lg n).

(Realistically, I would think that such a data structure would have a index accompanying it to indicate how many positions the array has been rotated.)

Edit: A search on Google takes me to this somewhat dated (but correct) topic on CodeGuru discussing the same problem. To add to my answer, I will copy some pseudocode that was given there so that it appears here with my solution (the thinking follows the same lines):

Search(set):
    if size of set is 1 and set[0] == item 
        return info on set[0]
    divide the set into parts A and B
    if A is sorted and the item is in the A's range
        return Search(A)
    if B is sorted and the item is in the B's range
        return Search(B)
    if A is not sorted
        return Search(A)
    if B is not sorted
        return Search(B)
    return "not found"

More Related Contents:

  1. How do I prove or disprove that this function is Ω(n^1.5)?
  2. How does a hash table work?
  3. How do I express mutually recursive data structures in safe Rust?
  4. Firebase data structure and url
  5. Implement graph-like data structure in Rust
  6. lenses, fclabels, data-accessor – which library for structure access and mutation is better
  7. Quadtree for 2D collision detection
  8. Advantages of Binary Search Trees over Hash Tables
  9. Difference between binary tree and binary search tree
  10. Data structure: insert, remove, contains, get random element, all at O(1)
  11. Are duplicate keys allowed in the definition of binary search trees?
  12. Efficient implementation of immutable (double) LinkedList
  13. Efficient (and well explained) implementation of a Quadtree for 2D collision detection [closed]
  14. Why hashmap lookup is O(1) i.e. constant time?
  15. What is the left-child, right-sibling representation of a tree? Why would you use it?
  16. Test whether a list contains a specific value in Clojure
  17. Difference between “Complete binary tree”, “strict binary tree”,”full binary Tree”?
  18. Chained Hash Tables vs. Open-Addressed Hash Tables
  19. Linked List vs Vector
  20. Data structure for quick time interval look up
  21. How does array work? How to create a basic array data structure using java? [closed]
  22. How would you implement an LRU cache in Java?
  23. What is copy-on-write?
  24. How to correctly use lists?
  25. design a stack such that getMinimum( ) should be O(1)
  26. Best algorithm to test if a linked list has a cycle
  27. What is a hash table and how do you make it in C? [closed]
  28. Algorithm for autocomplete?
  29. How to make a dictionary that returns key for keys missing from the dictionary instead of raising KeyError?
  30. How to restore the PriorityQueue to its initial state before the method call?

Leave a Comment