leetcode

commit b83f75100763fb0a6447f04913094aac0dd8a4b7
parent 570de43866205d3fc9a7f6a70c900642083b98f8
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri, 22 May 2026 08:27:17 +0300

33. search in rotated sorted array

Diffstat:
M
search_rotated_array.c
 | 
53
+++++++++++++++++++++++++++++++----------------------
A
search_rotated_array.py
 | 
44
++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 75 insertions(+), 22 deletions(-)
diff --git a/search_rotated_array.c b/search_rotated_array.c
@@ -1,6 +1,5 @@
 // 33. Search in Rotated Sorted Array
-#include <stdio.h>
-#include <stdlib.h>
+#include "leetcode.h"
 
 /*
  * there is an integer array 'nums' sorted in ascending order (with distinct
@@ -14,30 +13,40 @@
  * runtime complexity
  */
 
-int search(int *nums, int nums_size, int target) {
-  int left, right;
-  for (left = 0, right = nums_size - 1; left <= right;) {
-    int mid = (left + right) / 2;
-    if (nums[mid] == target)
-      return mid;
-    if (nums[left] <= nums[mid]) {
-      if (nums[left] <= target && target < nums[mid])
-        right = mid - 1;
-      else
-        left = mid + 1;
-    } else {
-      if (nums[mid] < target && target <= nums[right])
-        left = mid + 1;
-      else
-        right = mid - 1;
-    }
+int search(int *nums, int numsSize, int target) {
+  int low = 0, high = numsSize - 1;
+  while (low < high) {
+    int mid = (low + high) / 2;
+    if (nums[mid] > nums[high])
+      low = mid + 1;
+    else
+      high = mid;
+  }
+  int rot = low;
+  low = 0;
+  high = numsSize - 1;
+  while (low <= high) {
+    int mid = (low + high) / 2;
+    int real_mid = (mid + rot) % numsSize;
+    if (nums[real_mid] == target)
+      return real_mid;
+    if (nums[real_mid] < target)
+      low = mid + 1;
+    else
+      high = mid - 1;
   }
   return -1;
 }
 
 int main() {
   int n1[] = {4, 5, 6, 7, 0, 1, 2}, n2[] = {4, 5, 6, 7, 0, 1, 2}, n3[] = {1};
-  printf("%d\n", search(n1, 7, 0)); // expect: 4
-  printf("%d\n", search(n2, 7, 3)); // expect: -1
-  printf("%d\n", search(n3, 1, 0)); // expect: -1
+  int r1 = search(n1, ARRAY_SIZE(n1), 0);
+  int r2 = search(n2, ARRAY_SIZE(n2), 3);
+  int r3 = search(n3, ARRAY_SIZE(n3), 0);
+  printf("%d\n", r1);
+  assert(r1 == 4);
+  printf("%d\n", r2);
+  assert(r2 == -1);
+  printf("%d\n", r3);
+  assert(r3 == -1);
 }
diff --git a/search_rotated_array.py b/search_rotated_array.py
@@ -0,0 +1,44 @@
+# 33. Search in Rotated Sorted Array
+
+"""
+there is an integer array 'nums' sorted in ascending order (with distinct
+values). prior to being passed to your function, 'nums' is possibly rotated
+at an unknown pivot index 'k(1 <= k < nums.length)' such tht the resulting
+array is '[nums[k], nums[k + 1], ..., nums[n - 1], nums[0], nums[1], ...,
+nums[k - 1]]' (0-indxed). for example, '[0,1,2,4,5,6,7]' might be rotated at
+pivot index 3 and become '[4,5,6,7,0,1,2]'. given the array 'nums' after the
+possible rotation and an integer 'target', return the index of 'target' if it
+is in 'nums', or -1 otherwise. you must write an algorithm with 'O(log n)'
+runtime complexity
+"""
+
+
+class Solution:
+    def search(self, nums: List[int], target: int) -> int:
+        low, high = 0, len(nums) - 1
+        while low < high:
+            mid = (low + high) // 2
+            if nums[mid] > nums[high]:
+                low = mid + 1
+            else:
+                high = mid
+        rot = low
+        low = 0
+        high = len(nums) - 1
+        while low <= high:
+            mid = (low + high) // 2
+            real_mid = (mid + rot) % len(nums)
+            if nums[real_mid] == target:
+                return real_mid
+            if nums[real_mid] < target:
+                low = mid + 1
+            else:
+                high = mid - 1
+        return -1
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.search(nums=[4, 5, 6, 7, 0, 1, 2], target=0))
+    print(obj.search(nums=[4, 5, 6, 7, 0, 1, 2], target=3))
+    print(obj.search(nums=[1], target=0))