建立函数实现二分查找

以下是一个建立函数实现二分查找的例子：

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# 示例使用
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
if result != -1:
    print("查找成功，位置为", result)
else:
    print("查找失败")

相关问题

1．建立顺序查找表，并在此查找表上实现顺序查找操作。 2．建立有序顺序查找表，并在此查找表上实现二分查找操作。c语言

以下是一个简单的C语言实现顺序查找和二分查找的代码示例：

1. 顺序查找

#include <stdio.h>

#define MAX_SIZE 10

// 定义顺序查找函数
int seq_search(int *arr, int key, int len) {
    for (int i = 0; i < len; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1; // 如果未找到，则返回-1
}

int main() {
    int arr[MAX_SIZE] = {3, 1, 4, 5, 2, 9, 8, 7, 6, 0};
    int key = 5;
    int index = seq_search(arr, key, MAX_SIZE);
    if (index != -1) {
        printf("Key %d found at index %d\n", key, index);
    } else {
        printf("Key %d not found\n", key);
    }
    return 0;
}

2. 二分查找

#include <stdio.h>

#define MAX_SIZE 10

// 定义二分查找函数
int bin_search(int *arr, int key, int len) {
    int low = 0, high = len - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] > key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1; // 如果未找到，则返回-1
}

int main() {
    int arr[MAX_SIZE] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int key = 5;
    int index = bin_search(arr, key, MAX_SIZE);
    if (index != -1) {
        printf("Key %d found at index %d\n", key, index);
    } else {
        printf("Key %d not found\n", key);
    }
    return 0;
}

(1) 建立一个数据为整数的顺序表。根据用户输入的查找值，实现顺序表的顺序查找。 (2) 建立一个有序的整数构成的顺序表，根据用户输入的查找值，实现二分查找，并输出比较的元素，提示是否查找成功。要求实现递归和非递归算法。C++

好的，我已经了解了您的问题。下面是两个问题的解答：

1. 顺序查找

顺序查找的基本思想是从表的一端开始，逐个比较表中的元素，直到查找到或查找完为止。以下是顺序查找的代码实现：

#include<iostream>
using namespace std;

#define MAXSIZE 100    // 定义顺序表的最大长度

typedef struct {
    int data[MAXSIZE];  // 存放顺序表元素的数组
    int length;         // 记录顺序表的长度
}Sqlist;

// 顺序查找函数
int sequentialSearch(Sqlist L, int key) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == key) {
            return i;   // 返回查找值在顺序表中的下标
        }
    }
    return -1;          // 表示查找失败
}

int main() {
    Sqlist L;
    int key;
    cout << "请输入顺序表的长度：";
    cin >> L.length;
    cout << "请输入顺序表元素：";
    for (int i = 0; i < L.length; i++) {
        cin >> L.data[i];
    }
    cout << "请输入要查找的值：";
    cin >> key;
    int index = sequentialSearch(L, key);
    if (index == -1) {
        cout << "查找失败！" << endl;
    }
    else {
        cout << "查找成功，值为" << key << "的元素下标为：" << index << endl;
    }
    return 0;
}

2. 二分查找

二分查找也称为折半查找，是一种基于分治思想的查找算法。二分查找的前提条件是顺序表有序，基本思想是在查找过程中将查找区间逐渐缩小，直到找到查找值为止。以下是递归和非递归两种算法的代码实现：

#include<iostream>
using namespace std;

#define MAXSIZE 100    // 定义顺序表的最大长度

typedef struct {
    int data[MAXSIZE];  // 存放顺序表元素的数组
    int length;         // 记录顺序表的长度
}Sqlist;

// 非递归实现二分查找
int binarySearch(Sqlist L, int key) {
    int low = 0, high = L.length - 1;
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (L.data[mid] == key) {
            return mid;
        }
        else if (L.data[mid] > key) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return -1;
}

// 递归实现二分查找
int binarySearch(Sqlist L, int key, int low, int high) {
    if (low > high) {
        return -1;
    }
    int mid = (low + high) / 2;
    if (L.data[mid] == key) {
        return mid;
    }
    else if (L.data[mid] > key) {
        return binarySearch(L, key, low, mid - 1);
    }
    else {
        return binarySearch(L, key, mid + 1, high);
    }
}

int main() {
    Sqlist L;
    int key;
    cout << "请输入顺序表的长度：";
    cin >> L.length;
    cout << "请输入有序顺序表元素：";
    for (int i = 0; i < L.length; i++) {
        cin >> L.data[i];
    }
    cout << "请输入要查找的值：";
    cin >> key;
    int index1 = binarySearch(L, key);
    int index2 = binarySearch(L, key, 0, L.length - 1);
    if (index1 == -1) {
        cout << "非递归算法：查找失败！" << endl;
    }
    else {
        cout << "非递归算法：查找成功，值为" << key << "的元素下标为：" << index1 << endl;
    }
    if (index2 == -1) {
        cout << "递归算法：查找失败！" << endl;
    }
    else {
        cout << "递归算法：查找成功，值为" << key << "的元素下标为：" << index2 << endl;
    }
    return 0;
}

希望我的回答能够帮到您，如果您还有其他问题，请随时问我。