7-1 Binary Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

输入格式:

3 lines.
The first line means the number of the keys.
The second line consists several integers separated by commas.
The third line is the target value to search

输出格式:

1 line
If found, output the index of the target value, otherwise output -1.

输入样例:

在这里给出一组输入。例如：

1
2
3
7,
4,5,6,7,0,1,2
0

输出样例:

在这里给出相应的输出。例如：

1
4

代码

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
57
#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    scanf("%d,", &n);
    if (n == 0) {
        printf("-1");
        return 0;
    }
    int arr[n];
    for (int i = 0; i < n - 1; i++) {
        scanf("%d,", &arr[i]);
    }
    scanf("%d", &arr[n - 1]);
    int keyval;
    scanf("%d", &keyval);
    int keyidx = -1;
    //Search
    if (n == 1) {
        if (arr[0] == keyval) {
            keyidx = 0;
        }
        else {
            printf("-1");
            return 0;
        }
    }
    int left = 0, right = n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == keyval) {
            keyidx = mid;
            break;
        }
        else if (arr[left] <= arr[mid]) {
            if (arr[left] <= keyval && keyval < arr[mid]) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        else {
            if (arr[mid] < keyval && keyval <= arr[right]) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
    }
    printf("%d", keyidx);
    return 0;
}

7-2 Search a 2D Matrix

Using an efficient algorithm (e.g., binary search) to search for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

输入格式:

The first line contains two integers m, n which are the numbers of the rows and columns, respectivley.
Then follows m lines which is an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
The last line is the target value to search.

输出格式:

1 line
If found, output true, otherwise output false.

输入样例:

在这里给出一组输入。例如：

1
2
3
4
5
6
4,6
1,3,5,7,8,9,
10,11,13,16,17,20,
23,30,33,34,50,51,
53,60,63,64,70,75,
11

输出样例:

在这里给出相应的输出。例如：

1
true

代码

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
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <stdlib.h>

// Perform a binary search on the given array to find the target value
int binarySearch(int* nums, int len, int target) {
    int low = 0, high = len - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] > target) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

// Search for the target value in the matrix using binary search
int searchMatrix(int** matrix, int rows, int cols, int target) {
    if (rows == 0 || cols == 0) return -1;

    // Use binary search to find the row in which the target value is likely to be located
    int low = 0, high = rows - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (matrix[mid][0] <= target && matrix[mid][cols - 1] >= target) {
            // The target value is likely to be in the current row, so perform binary search on this row
            return binarySearch(matrix[mid], cols, target);
        }
        if (matrix[mid][0] > target) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

int main() {
    int rows, cols;
    scanf("%d,%d\n", &rows, &cols);

    // Create the matrix using dynamic memory allocation
    int** matrix = (int**) malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; i++) {
        matrix[i] = (int*) malloc(cols * sizeof(int));
    }

    // Read the matrix from input
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            scanf("%d,", &matrix[i][j]);
        }
    }
    int target;
    scanf("%d", &target);

    // Search for the target value in the matrix
    int result = searchMatrix(matrix, rows, cols, target);
    if (result == -1) printf("false\n");
    else printf("true\n");

    // Free the memory allocated for the matrix
    for (int i = 0; i < rows; i++) {
        free(matrix[i]);
    }
    free(matrix);

    return 0;
}