Tag C rotated array

Minimum in a Sorted and Rotated Array in C: A Comprehensive Tutorial

Given a sorted array of distinct elements that has been rotated at some unknown point, the task is to find the minimum element. This is a classic binary search problem that tests your understanding of rotated arrays and efficient search techniques. The minimum element marks the rotation point and is the only element smaller than its predecessor.

This tutorial provides an in-depth exploration of finding the minimum in a sorted and rotated array in C: naive linear search, optimized binary search, practical implementation, common pitfalls, and best practices.

Conceptual Introduction & Fundamentals

What is a Sorted and Rotated Array?

A sorted array that has been rotated at some pivot point. The array consists of two sorted subarrays.

Example:

text

Original sorted: [1, 2, 3, 4, 5, 6] Rotated: [5, 6, 1, 2, 3, 4]

The minimum element 1 is at the rotation point.

Key Insight

In a sorted and rotated array:

• The array is divided into two sorted parts.
• The minimum element is the only element smaller than its predecessor.
• The minimum element marks the rotation pivot.

Why This Problem Matters

• Binary search variants: Classic rotated array problem.
• Search optimization: O(n) to O(log n) transformation.
• Algorithm design: Teaches divide-and-conquer.
• Interview preparation: Common coding interview question.
• Rotated array operations: Foundation for searching in rotated arrays.

Approaches Overview

Syntax & Core Mechanics

Approach 1: Linear Search (Naive)

Traverse the entire array to find the minimum.

c

#include <stdio.h> int findMinLinear(const int arr[], int n) { if (n <= 0) return -1; int min = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] < min) { min = arr[i]; } } return min; } int main(void) { int arr[] = {5, 6, 1, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("Minimum: %d\n", findMinLinear(arr, n)); return 0; }

Expected output:

text

Minimum: 1

Time: O(n), Space: O(1)

Approach 2: Binary Search (Optimized)

Use binary search to find the minimum in O(log n).

Steps:

1. If arr[low] < arr[high], the range is sorted; return arr[low].
2. Compute mid.
3. If arr[mid] > arr[high], minimum is in the right half; low = mid + 1.
4. Otherwise, minimum is at mid or left; high = mid.
5. When low == high, that index holds the minimum.

c

#include <stdio.h> int findMinBinary(const int arr[], int n) { if (n <= 0) return -1; int low = 0; int high = n - 1; while (low < high) { /* If current range is sorted, first element is minimum */ if (arr[low] < arr[high]) { return arr[low]; } int mid = low + (high - low) / 2; /* Minimum lies in right half */ if (arr[mid] > arr[high]) { low = mid + 1; } /* Minimum lies at mid or left half */ else { high = mid; } } /* low == high points to minimum element */ return arr[low]; } int main(void) { int arr[] = {5, 6, 1, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); printf("Minimum: %d\n", findMinBinary(arr, n)); return 0; }

Expected output:

text

Minimum: 1

Time: O(log n), Space: O(1)

Alternative: Finding Minimum Index

c

#include <stdio.h> int findMinIndex(const int arr[], int n) { if (n <= 0) return -1; int low = 0; int high = n - 1; while (low < high) { if (arr[low] < arr[high]) { return low; } int mid = low + (high - low) / 2; if (arr[mid] > arr[high]) { low = mid + 1; } else { high = mid; } } return low; } int main(void) { int arr[] = {5, 6, 1, 2, 3, 4}; int n = sizeof(arr) / sizeof(arr[0]); int index = findMinIndex(arr, n); printf("Minimum: %d at index %d\n", arr[index], index); return 0; }

Expected output:

text

Minimum: 1 at index 2

Full Practical Code Example with Explanation

This program demonstrates both approaches with verification, performance comparison, and edge cases.

Program: Minimum in Sorted and Rotated Array

c

/** * min_sorted_rotated.c * Finds the minimum element in a sorted and rotated array. * Compares linear and binary search approaches. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <limits.h> #include <time.h> #define MAX_LINE_LEN 100 #define MAX_SIZE 100000 /* Function prototypes */ int findMinLinear(const int arr[], int n); int findMinBinary(const int arr[], int n); int findMinIndex(const int arr[], int n); int readInteger(const char *prompt, int *outValue); void printArray(const int arr[], int n); void rotateArray(int arr[], int n, int d); void demonstrateApproaches(void); void performanceComparison(void); void demonstrateEdgeCases(void); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Minimum in Sorted and Rotated Array ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Demonstrate with Sample Arrays\n"); printf("2. Enter Custom Array\n"); printf("3. Performance Comparison\n"); printf("4. Edge Cases\n"); printf("5. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateApproaches(); break; case 2: { int arr[MAX_SIZE]; int n; if (readInteger("Enter array size (1-100000): ", &n) != 0) { fprintf(stderr, "Invalid size.\n"); break; } if (n < 1 || n > MAX_SIZE) { printf("Size must be 1-%d.\n", MAX_SIZE); break; } printf("Enter %d elements (sorted then rotated):\n", n); for (int i = 0; i < n; i++) { char prompt[50]; snprintf(prompt, sizeof(prompt), " Element %d: ", i); if (readInteger(prompt, &arr[i]) != 0) { fprintf(stderr, "Invalid input.\n"); n = i; break; } } printf("\nArray: "); printArray(arr, n); int linear = findMinLinear(arr, n); int binary = findMinBinary(arr, n); printf("Minimum (linear): %d\n", linear); printf("Minimum (binary): %d\n", binary); printf("Verification: %s\n", (linear == binary) ? "PASS" : "FAIL"); break; } case 3: performanceComparison(); break; case 4: demonstrateEdgeCases(); break; case 5: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Linear search: O(n) */ int findMinLinear(const int arr[], int n) { if (n <= 0) return INT_MAX; int min = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] < min) { min = arr[i]; } } return min; } /* Binary search: O(log n) */ int findMinBinary(const int arr[], int n) { if (n <= 0) return INT_MAX; int low = 0; int high = n - 1; while (low < high) { /* If current range is sorted, first element is minimum */ if (arr[low] < arr[high]) { return arr[low]; } int mid = low + (high - low) / 2; /* Minimum lies in right half */ if (arr[mid] > arr[high]) { low = mid + 1; } /* Minimum lies at mid or left half */ else { high = mid; } } return arr[low]; } /* Finds index of minimum element */ int findMinIndex(const int arr[], int n) { if (n <= 0) return -1; int low = 0; int high = n - 1; while (low < high) { if (arr[low] < arr[high]) { return low; } int mid = low + (high - low) / 2; if (arr[mid] > arr[high]) { low = mid + 1; } else { high = mid; } } return low; } /* Rotates array right by d positions */ void rotateArray(int arr[], int n, int d) { if (n <= 1) return; d %= n; if (d == 0) return; int *temp = malloc(n * sizeof(int)); if (temp == NULL) return; for (int i = 0; i < n; i++) { temp[(i + d) % n] = arr[i]; } for (int i = 0; i < n; i++) { arr[i] = temp[i]; } free(temp); } /* Prints array */ void printArray(const int arr[], int n) { printf("["); for (int i = 0; i < n; i++) { printf("%d", arr[i]); if (i < n - 1) printf(", "); } printf("]\n"); } /* Demonstrates both approaches */ void demonstrateApproaches(void) { printf("\n=== Sample Arrays ===\n"); int arr1[] = {5, 6, 1, 2, 3, 4}; int n1 = sizeof(arr1) / sizeof(arr1[0]); printf("\nArray 1: "); printArray(arr1, n1); printf("Linear: %d\n", findMinLinear(arr1, n1)); printf("Binary: %d\n", findMinBinary(arr1, n1)); printf("Index: %d\n", findMinIndex(arr1, n1)); int arr2[] = {3, 1, 2}; int n2 = sizeof(arr2) / sizeof(arr2[0]); printf("\nArray 2: "); printArray(arr2, n2); printf("Linear: %d\n", findMinLinear(arr2, n2)); printf("Binary: %d\n", findMinBinary(arr2, n2)); int arr3[] = {4, 2, 3}; int n3 = sizeof(arr3) / sizeof(arr3[0]); printf("\nArray 3: "); printArray(arr3, n3); printf("Linear: %d\n", findMinLinear(arr3, n3)); printf("Binary: %d\n", findMinBinary(arr3, n3)); int arr4[] = {1, 2, 3, 4, 5}; int n4 = sizeof(arr4) / sizeof(arr4[0]); printf("\nArray 4 (not rotated): "); printArray(arr4, n4); printf("Linear: %d\n", findMinLinear(arr4, n4)); printf("Binary: %d\n", findMinBinary(arr4, n4)); int arr5[] = {2, 3, 4, 5, 1}; int n5 = sizeof(arr5) / sizeof(arr5[0]); printf("\nArray 5: "); printArray(arr5, n5); printf("Linear: %d\n", findMinLinear(arr5, n5)); printf("Binary: %d\n", findMinBinary(arr5, n5)); } /* Performance comparison */ void performanceComparison(void) { printf("\n=== Performance Comparison (n = 100000) ===\n"); int size = 100000; int *arr = malloc(size * sizeof(int)); if (arr == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } /* Create sorted array then rotate */ for (int i = 0; i < size; i++) { arr[i] = i + 1; } rotateArray(arr, size, 12345); printf("Array size: %d, Rotated by: 12345\n\n", size); clock_t start, end; double timeTaken; /* Linear search */ start = clock(); int linearResult = findMinLinear(arr, size); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Linear (O(n)): Min = %d, Time = %.3f ms\n", linearResult, timeTaken); /* Binary search */ start = clock(); int binaryResult = findMinBinary(arr, size); end = clock(); timeTaken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000.0; printf("Binary (O(log n)): Min = %d, Time = %.3f ms\n", binaryResult, timeTaken); printf("\nVerification: %s\n", (linearResult == binaryResult) ? "PASS" : "FAIL"); free(arr); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: Single element */ int arr1[] = {42}; printf("Case 1: Single element\n"); printf(" Array: "); printArray(arr1, 1); printf(" Min: %d\n", findMinBinary(arr1, 1)); /* Case 2: Two elements, rotated */ int arr2[] = {2, 1}; printf("\nCase 2: Two elements, rotated\n"); printf(" Array: "); printArray(arr2, 2); printf(" Min: %d\n", findMinBinary(arr2, 2)); /* Case 3: Two elements, sorted */ int arr3[] = {1, 2}; printf("\nCase 3: Two elements, sorted\n"); printf(" Array: "); printArray(arr3, 2); printf(" Min: %d\n", findMinBinary(arr3, 2)); /* Case 4: Already sorted */ int arr4[] = {1, 2, 3, 4, 5}; printf("\nCase 4: Already sorted (not rotated)\n"); printf(" Array: "); printArray(arr4, 5); printf(" Min: %d\n", findMinBinary(arr4, 5)); /* Case 5: Rotated by n-1 (minimum at end) */ int arr5[] = {2, 3, 4, 5, 1}; printf("\nCase 5: Rotated by n-1 (minimum at end)\n"); printf(" Array: "); printArray(arr5, 5); printf(" Min: %d\n", findMinBinary(arr5, 5)); /* Case 6: Rotated by 1 (minimum at index 1) */ int arr6[] = {5, 1, 2, 3, 4}; printf("\nCase 6: Rotated by 1 (minimum at index 1)\n"); printf(" Array: "); printArray(arr6, 5); printf(" Min: %d\n", findMinBinary(arr6, 5)); /* Case 7: Negative numbers */ int arr7[] = {-3, -2, -1, -5, -4}; printf("\nCase 7: Negative numbers\n"); printf(" Array: "); printArray(arr7, 5); printf(" Min: %d\n", findMinBinary(arr7, 5)); } /* Reads an integer safely */ int readInteger(const char *prompt, int *outValue) { char buffer[MAX_LINE_LEN]; char *endPtr; long val; printf("%s", prompt); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { return -1; } errno = 0; val = strtol(buffer, &endPtr, 10); if (endPtr == buffer || (*endPtr != '\n' && *endPtr != '\0')) { return -1; } if (errno == ERANGE || val < -2147483647 - 1 || val > 2147483647) { return -1; } *outValue = (int)val; return 0; }

Explanation of Approaches

1. Linear Search: Traverse entire array; O(n).
2. Binary Search: Uses sorted range detection; O(log n).
3. Index variant: Returns the index of the minimum element.

Expected Output (sample run)

text

=== Minimum in Sorted and Rotated Array === --- Menu --- 1. Demonstrate with Sample Arrays 2. Enter Custom Array 3. Performance Comparison 4. Edge Cases 5. Exit Enter choice: 1 === Sample Arrays === Array 1: [5, 6, 1, 2, 3, 4] Linear: 1 Binary: 1 Index: 2 Array 2: [3, 1, 2] Linear: 1 Binary: 1 Array 3: [4, 2, 3] Linear: 2 Binary: 2 Array 4 (not rotated): [1, 2, 3, 4, 5] Linear: 1 Binary: 1 Array 5: [2, 3, 4, 5, 1] Linear: 1 Binary: 1 --- Menu --- ... Enter choice: 3 === Performance Comparison (n = 100000) === Array size: 100000, Rotated by: 12345 Linear (O(n)): Min = 1, Time = 0.398 ms Binary (O(log n)): Min = 1, Time = 0.001 ms Verification: PASS --- Menu --- ... Enter choice: 4 === Edge Cases === Case 1: Single element Array: [42] Min: 42 Case 2: Two elements, rotated Array: [2, 1] Min: 1 Case 3: Two elements, sorted Array: [1, 2] Min: 1 Case 4: Already sorted (not rotated) Array: [1, 2, 3, 4, 5] Min: 1 Case 5: Rotated by n-1 (minimum at end) Array: [2, 3, 4, 5, 1] Min: 1 Case 6: Rotated by 1 (minimum at index 1) Array: [5, 1, 2, 3, 4] Min: 1 Case 7: Negative numbers Array: [-3, -2, -1, -5, -4] Min: -5

Common Pitfalls, Edge Cases & Memory Considerations

1. Empty Array

Accessing arr[0] on an empty array is undefined behavior.

c

if (n <= 0) return INT_MAX; /* Required */

Solution: Check n <= 0 before processing.

2. Single Element

A single-element array has that element as minimum.

c

int arr[] = {42}; /* Minimum = 42 */

Solution: Handle n == 1 correctly.

3. Already Sorted Array

The arr[low] < arr[high] check handles this case.

c

/* If sorted, returns arr[low] immediately */

4. Duplicate Elements

Duplicates can break binary search assumptions.

c

int arr[] = {2, 2, 0, 2, 2}; /* Ambiguous */

Solution: For duplicates, fall back to linear search.

5. Using <= Instead of <

Using arr[low] <= arr[high] may cause incorrect results with duplicates.

c

if (arr[low] < arr[high]) /* Correct for distinct elements */

6. Off-by-One in Mid Calculation

(low + high) / 2 can overflow.

c

int mid = low + (high - low) / 2; /* Correct */

7. Infinite Loop

Incorrect high = mid - 1 can skip the minimum.

c

high = mid; /* Correct: keep mid in search range */

8. Wrong Return Value

Returning arr[low] after loop vs. inside loop.

c

while (low < high) { ... } return arr[low]; /* Correct */

9. Negative Numbers

Negative numbers work correctly with the algorithm.

c

int arr[] = {-3, -2, -1, -5, -4}; /* Minimum = -5 */

10. Memory Considerations

• Both approaches use O(1) extra space.
• No dynamic allocation required.
• Array size should fit in int or size_t.
• Binary search preferred for large arrays.

Summary & Best Practices

Finding the minimum in a sorted and rotated array is a classic binary search problem. The minimum marks the rotation pivot and is the only element smaller than its predecessor.

Key Takeaways

• Sorted and rotated array has two sorted parts.
• Minimum element is at the rotation point.
• Linear search: O(n) time.
• Binary search: O(log n) time.
• Key check: arr[low] < arr[high] means sorted range.
• Use high = mid (not mid - 1) to keep minimum in range.

Best Practices

1. Use binary search for O(log n) performance.
2. Check n <= 0 for empty arrays.
3. Use arr[low] < arr[high] to detect sorted ranges.
4. Use low + (high - low) / 2 to avoid overflow.
5. Use high = mid (not mid - 1) to keep minimum in range.
6. Test with edge cases: empty, single, sorted, rotated by n-1.
7. Handle duplicates with linear fallback if needed.
8. Use INT_MAX for error return on empty arrays.
9. Verify with naive approach during testing.
10. Document rotation direction (this problem assumes right rotation).

By mastering this problem, you’ll understand binary search variations and be prepared for related problems like searching in rotated sorted arrays and finding rotation counts.