Searching For a Number in Shifted Sorted Array within O(log(n)) time

Run into the algorithm problem long time ago. Now post my answer here. A sorted array, say: {1,2,3,4,5,6,7,8,9,10,11,12}, do right rotate through carry unknown times, and then it might become: {6,7,8,9,10,11,12,1,2,3,4,5}. Now we need get the index of a given number, say 4, from the array within O(log(n)) time. Apparently a 8-year-old can get it…

1

Selecting median of two sorted arrays

In this post, I’d like to discuss one interesting algorithm problem which took me quite a while to find an ideal solution. The problem is as followings: Array A and B are sorted with length of m and n respectively. Try to select median of the two arrays within O(log(m+n)) time. For example, A =…

4