First let me say that I am new to C so my approach is basic. I am attempting to check a sorted array for a point where it was rotated. For example (1 2 4 5 9) becomes (5 9 1 2 4). I am attempting to "split" the array into two sub arrays and check one starting from [0] and increasing by one and one starting from [4] and decreasing by one. Here is what I have so far:

```
#define size 5
int main(void)
{
int x, i, j, start, end;
int array1[size]= {4, 8, 0, 1, 3};
start = 0;
end = size -1;
while(start < end)
{
if (array1[start] < array1[end])
start++;
end--;
```

I guess some of the questions I am having is if my approach is good (outside to inside) or if I should start in the middle and work my way out. Also how would I code the determination for where the pivot actually happens. I see a few answers for C++ in SO however I am not seeing many that are clear for C so I figured I'd ask. Any advice is appreciated.

The problem is rather trivial to solve. Since the original set is sorted, just iterate forward until the element you hit is less than the final element in the array -- this was the original first element, so you know that its distance from the start is congruent to *R (mod N)* where *R* is the rotation distance and *N* is `size`

.

```
int last = array[size - 1];
int r;
for (r = 0; array[r] >= last; ++r) ;
int pivot = array[r];
/* pivot was the original array[0] */
```

Code for finding pivot element in C

```
int findPivot(int arr[], int low, int high)
{
// base cases
if (high < low) return -1;
if (high == low) return low;
int mid = (low + high)/2; /*low + (high - low)/2;*/
if (mid < high && arr[mid] > arr[mid + 1])
return mid;
if (mid > low && arr[mid] < arr[mid - 1])
return (mid-1);
if (arr[low] >= arr[mid])
return findPivot(arr, low, mid-1);
else
return findPivot(arr, mid + 1, high);
}
```

where you return -1 when array is already sorted, rest of the things as usual like a binary search

Similar Questions

I am trying to write a simple algorithm for moving the elements around pivot such that the elements on the left of pivot is smaller than the pivot and the element on the right of pivot is greater than

I have recently recieved a question from a university that i'm studying to build a class named point. one of the class methods has a isAbove() function which compares 2 points Y-axis. the higher y-axi

standard scaling using the center of an image as the pivot point and is uniform in all dimensions. I'd like to figure out a way to scale an image from an arbitrary pivot point such that points closer

I am trying to point a pointer to a calloc array. For some reason, when I reach the second element the program force quits. The first element prints out and works fine. Here is an example of my code j

I would like to write a piece of code for inserting a number into a sorted array at the appropriate position (i.e. the array should still remain sorted after insertion) My data structure doesn't allow

If I have a 2D rectangle of type Microsoft.XNA.Framework.Rectangle and I want to see if a point on screen (defined as (x,y)) goes through it after it has also been rotated by a certain amount?

for a M X M array what is the time complexity of finding an element assuming the array is sorted in all the direction?

We have sorted array arr[]={2,4,5,7,8,12,16,18,20}. We need to find out pair of elements whose addition is 12, with complexity O(n). Could anyone help on it?

I'm given the rotated RectangleGeometry and I need to find the top-left and bottom-right points. What would be the fastest way to accomplish that? Please notice, that I don't want these points for AAB

I am looking for C algorithms (or code) that implement fast sorted integer array intersection/union operations. The faster, the better. In other words, what's an efficient way in C to implement union

Skiena, in The Algorithm Design Manual, states that insertion into a sorted array is O(n). Yet searching for an item in a sorted array is O(log n), because you can do a binary search. Couldn't inserti

In a constructor I am trying to build an array of Point2D.Double from an Point2D array. Basically I want to add coordinates to a graph. I did this: private Point2D.Double [] points; public EmbeddedGra

I am now trying some stuff with PCA but it's very important for me to know which are the features responsible for each eigenvalue. numpy.linalg.eig gives us the diagonal matrix already sorted but I w

I have a hashmap, I wish to get an array of the keys in this hashmap, but I wish for the array to be sorted. For instance if the map looks like this: <2,obj1> <4,obj2> <6,obj3>

I have the the following array of numbers in Ruby (higher is better), and I'd like to rank them. In other words, I want to convert the following sorted list: [89 52 52 36 18 18 5] to the following ra

Possible Duplicate: Fastest strategy to form and sort an array of positive integers What would be the fastest way to get a sorted array from an unsorted iterable of integers ? Currently I do it by i

I already read this post but the answer didn't satisfied me Check if Array is sorted in Log(N). Imagine I have a serious big array over 1,000,000 double numbers (positive and/or negative) and I want

I am currently studying quicksort and would like to know how it works when the first (or last) element is chosen as the pivot point. Say for example I have the following array: {15, 19, 34, 41, 27, 13

I have an array of points with distances. I wish to find a point that best satisfies the condition that for (point_i, distance_i) in pointArray: abs(point - point_i) = distance_i I think this could

I am getting values which are sorted from a plist and displaying them in a tableview. I am providing the capability of entering a custom category which will be written to plist. But I want that to be

I have an array of sorted ints with a 1,000 or more values (could be up to 5000+). I need to write a function that receives an int and returns a bool based on the element being in the array. I know I

I was asked this interview question recently: You're given an array that is almost sorted, in that each of the N elements may be misplaced by no more than k positions from the correct sorted order. F

Yet another interview question asked me to find the maximum possible subarray of repeated values given a sorted array in shortest computational time possible. Let input array be A[1 ... n] Find an arr

I am trying to convert the output buffer(character array) of the code below to floating point format for further calculations. Can anybody tell me how to do it. #include usbtmc.h #include <errno.

How to test if a point P = [xp,yp] is inside/outside some rotated ellipse given by the centre C=[x,y], a, b, and phi ( angle of rotation)? At this moment I am using the following solution: rotate elli

I have a problem with finding/soritng points in array. When I want to find the point which is the nearest to the base point (0,0): CvPoint2D32f[] corners; ... Cv.FindChessboardCorners(...) ... int min

I've been tasked with creating a method that will print all the indices where value x is found in a sorted array. I understand that if we just scanned through the array from 0 to N (length of array)

I tried finding the sum of all numbers of a nested array, but I don't get it to work correctly. This is what I tried: function arraySum(i) { sum=0; for(a=0;a<i.length;a++){ if(typeof i[a]==number

Given an array A which holds a permutation of 1,2,...,n. A sub-block A[i..j] of an array A is called a valid block if all the numbers appearing in A[i..j] are consecutive numbers (may not be in order.

While preparing for tech interview I stumbled upon this interesting question: You've been given an array that is sorted and then rotated. example Let arr = [1,2,3,4,5] which is sorted and then rotated

I have try many things without finding the good solution so here I am. In my game (2D) I have to check collision with all my Object (house, garage..) which are image inside Rotated Rectangle, between

Given an binary mask with an object in Matlab. I am going to find the concavity point of the object boundary. The concavity point I mean here is the deepest concavity point with respect to the Euclide

I am using the following code to find a point of coordinates exists in the code or not: mMap.setOnMapClickListener(new OnMapClickListener() { public void onMapClick(LatLng point) { boolean checkPoly =

I have a vector storing the distance to certain reference point along a line. So, I want for example the index where distance is 700 meters or the nearest value to that distance. I have asumed the vec

In this post Why is processing a sorted array faster than random array, it says that branch predicton is the reason of the performance boost in sorted arrays. But I just tried the example using Python

I have a problem to find the touch point. I have a function loadView() where I set 16 tiles(16 UIImageView). Then In function: - (void) touchesBegan:(NSSet*)touches withEvent:(UIEvent*)event { // Retr

Suddenly, for some reason, objects in the unity editor started rotating around their center of gravity (at least that's what I think is going on) instead of their pivot point. I tried placing the obje

I want to write a loopless program (probably using comprehension) to remove duplicate elements in a sorted array in Python (and most efficiently too).

Description: Given two sorted arrays (none-descending), find the Kth min element in T = O(lg(m + n)), m and n are length of two arrays, respectively. Question: Do not understand the algorithm below a

I have an array where I'm trying to find the unique values. I've seen many answers for this type of thing, but I can't understand how to apply them to my situation. Thanks in advance for the help, as

The question is pretty much what the title says, with a slight variation. If I remember correctly, finding an entry in an array of size 'n' has as the average case the complexity O(n). I assume that

I want to implement an algorithm that inserts sorted arrays into binary search trees but I don't want ending up with a tree that only grows to one side. Do you have any ideas? Thanks.

I have 20-items array which contains decimal numbers. They are unsorted. On every iteration only several items of the array change (~1-3 items of 20-items array). After each iteration I need to have t

Is it possible to define a fallback or an else case for a PIVOT operation? Let me play with the sample from MSDN: -- Pivot table with one row and five columns SELECT 'AverageCost' AS Cost_Sorted_B

Here is a code pasted from here I'm unable to understand what it is doing. I could think of a simple algorithm to find median of two sorted arrays when merged. The idea is to compare the medians (m1,

Hi I want to sort an array of point objects in javascript so that the array, [{x: 220, y: 1080}, {x: 1, y: 0}, {x: 0, y: 1080}] becomes [{x: 0, y: 1080}, {x: 1, y: 0}, {x: 220, y: 1080}] Thanks in adv

I am writing the code for peak finding algorithm for a 1D array. I have read this post Peak finding algorithm. This is exactly what I am trying to do, there is discussion about time complexity but not

In Java SE 7, I'm trying to solve a problem where I have a series of Rectangles. Through some user interaction, I get a Point. What I need to do is find the (first) Rectangle which contains the Point

I have a sorted array of 5000 integers. How fast can I tell if a random integer is a member of the array? An answer in general, C and Ruby would be nice. The array values are of the form c * c + 1 w

I need to read sorted array from input to awk/gawk and get median. I don't want to store the whole array and am trying to get constant space for the calculation. Are you aware of any algorithm doing t