顺序表综合操作

  1. 线性表(a1,a2,a3…an)中的元素递增有序且按顺序存储与计算机内，
  2. 要求设计一个算法完成用最少时间在表中查找数值为x的元素，若找到则将其与后继元素位置相互交换，若找不到则将其插入表中并使表中元素仍然递增有序

1.二分查找递归

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
#include "preset.h"

//有序顺序表查找（二分查找）递归写法
int binSearch(SqList sql, int target, int low, int high) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    cout << "low : " << low << " high : " << high << " mid : " << mid << endl;
    if (target == sql.elem[mid]) {
        return mid;
    } else if (target < sql.elem[mid]) {
        high = mid - 1;
        binSearch(sql, target, low, high);
    } else {
        low = mid + 1;
        binSearch(sql, target, low, high);
    }
}

int main() {
    SqList sql = {{1, 3, 5, 7, 8, 10, 11}, 7};
    cout << "current List:" << endl; print(sql);
    int target; cin >> target;
    cout << binSearch(sql, target, 0, sql.length - 1) << endl;
    return 0;
}

2.二分查找非递归

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
#include "preset.h"

//有序顺序表查找（二分查找）非递归写法
int binSearch(SqList sql, int target) {
    int low = 0;
    int high = sql.length - 1;
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        cout << "low : " << low << " high : " << high << " mid : " << mid << endl;
        if (target == sql.elem[mid]) {
            return mid;
        } else if (target < sql.elem[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

int main() {
    SqList sql = {{1, 3, 5, 7, 8, 10, 11}, 7};
    cout << "current List:" << endl; print(sql);
    int target; cin >> target;
    cout << binSearch(sql, target) << endl;
    return 0;
}

3.二分查找+顺序表插入

  1. 线性表中的元素递增有序,用最少时间在表中查找数值为x的元素
  2. 若找到 则将其与后继元素位置 相交换
  3. 若未找到 则将其插入表中 并使表中元素仍递增有序
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
#include "preset.h"

//有序顺序表查找（二分查找）
void binSearch(SqList &sql, int target) {
    int low = 0;
    int high = sql.length - 1;
    int mid;
    int flag = 0;
    while (low <= high) {
        mid = (low + high) / 2;
        if (target == sql.elem[mid]) {
            flag = 1; break;
        } else if (target < sql.elem[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    //[修改]若找到 则将其与后继元素位置 相交换
    if (flag && mid != sql.length) {
        int temp = sql.elem[mid];
        sql.elem[mid] = sql.elem[mid + 1];
        sql.elem[mid + 1] = temp;
    }
    //[插入]若未找到 则将其插入表中 并使表中元素仍递增有序
    if (high < low) {
        int i;
        for (i = sql.length - 1; i > high; --i) {
            sql.elem[i + 1] = sql.elem[i];
        }
        sql.elem[i + 1] = target;
        sql.length++;
    }
}

int main() {
    SqList sql = {{1, 3, 5, 7, 8, 10, 11}, 7};
    cout << "current List:" << endl; print(sql);
    int target; cin >> target;
    binSearch(sql, target);
    cout << "current List:" << endl; print(sql);
    return 0;
}