aboutsummaryrefslogtreecommitdiff
path: root/search_rotated_array2.c
blob: cf38e3a9f5317dea09571baac334021788a35120 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 81. Search in Rotated Sorted Array II
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

/*
 * there is an integer array 'nums' sorted in non-decreasing order (not
 * necessarily with distinct values). before being passed to your function,
 * 'nums' is rotated at an unknown pivot index 'k(0 <= k < nums.length)' such
 * that the resulting array is '[nums[k], nums[k + 1], ..., nums[n - 1],
 * nums[0], nums[1], ..., nums[k - 1]]' (0-indexed). for example
 * '[0,1,2,4,4,4,5,6,6,7]' might be rotated at a pivot index 5 and become
 * '[4,5,6,6,7,0,1,2,4,4]'. given the array 'nums' after the rotation and an
 * integer 'target', return true if 'target' is in 'nums' of 'false' if it is
 * not in 'nums'. you must decrease the overall operation steps as much as
 * possible.
 */

int find_min(int *nums, int nums_size) {
  int min_idx = 0;
  for (int i = 0; i + 1 < nums_size; i++)
    if (nums[i + 1] < nums[i]) {
      min_idx = i + 1;
      break;
    }
  return min_idx;
}

bool search(int *nums, int nums_size, int target) {
  if (nums_size == 1)
    return nums[0] == target ? 1 : 0;
  int start = find_min(nums, nums_size), end = start + nums_size;
  int arr_size = 2 * nums_size;
  int *arr = (int *)malloc(arr_size * sizeof(int));
  for (int i = 0; i < arr_size; i++)
    arr[i] = nums[i % nums_size];
  bool is_find = false;
  while (start < end) {
    int mid = start + (end - start) / 2;
    if (target == arr[mid]) {
      is_find = true;
      break;
    } else if (target < arr[mid])
      end = mid;
    else
      start = mid + 1;
  }
  free(arr);
  return is_find;
}

int main() {
  int nums[] = {2, 5, 6, 0, 0, 1, 2}, nums_size = 7;
  printf("%d\n", search(nums, nums_size, 0)); // expect: 1
  printf("%d\n", search(nums, nums_size, 3)); // expect: 0
}