Huge Lemon的博客

有序循环数组查找值

2020-02-12

有序循环数组查找指定值

题目描述

一个有序循环数组array[]，不知其升序还是降序，也不知其起点在哪里。请编程寻找指定元素。

思路

  1. 先通过中间值和最后一个或者第一个元素比较，找出局部有序范围，再通过二分查找局部有序段
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int sortArrFindOne(int arr[], int low, int high, int target) {
    int mid = (high + low) / 2;
    if(arr[mid] == target)
        return mid;
    if (arr[mid] < arr[high]) {
        if (arr[mid] < target && target <= arr[high]) {
            return find(arr, mid, high, target);
        } else {
            return sortArrFindOne(arr, low, mid, target);
        }
    } else {
        if (arr[low] <= target && target < arr[mid]) {
            return find(arr, low, mid, target);
        } else {
            return sortArrFindOne(arr, mid, high, target);
        }
    }
}
  1. 找局部有序（二分递归查找）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int find(int arr[], int low, int high, int target) {
        int mid = (high - low) / 2  + low;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) {
            return find(arr, mid + 1, high, target);
        } else {
            return find(arr, low, mid - 1, target);
        }
    }
Tags: 算法 LeetCode
← 反转字符串中的单词 III 删除链表的倒数第N个节点 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏