顺序表顺序查找折半查找算法

顺序表和折半查找算法是两种不同的数据结构和查找方法。

**顺序表**：
顺序表是一种线性数据结构，其中元素在内存中是连续存储的，可以通过下标直接访问任意位置的元素。顺序查找（也称为线性查找）是最基础的查找算法，其基本思路是从第一个元素开始，逐个比较每个元素的值，直到找到目标值或遍历完整个列表。这种方法的时间复杂度是O(n)，其中n是列表的长度，因为最坏情况下可能需要检查所有元素。

**折半查找（Binary Search）**：
这是一种在有序列表中查找特定元素的搜索算法。它基于分治策略，首先将查找区间缩小一半。查找过程从中间元素开始，如果目标值大于中间元素，则在右侧子数组中继续查找；如果目标值小于中间元素，则在左侧子数组中查找；如果相等则返回该位置。每次都能排除一半的元素，直到找到目标或区间为空。折半查找的时间复杂度为O(log n)，效率远高于顺序查找，但前提是列表必须是有序的。

相关问题

数据结构顺序表的顺序查找和折半查找c++代码

顺序查找（Sequential Search）也被称为线性查找，它是一种简单直观的查找方式。顺序查找从数据结构的起始位置开始，依次比较每个元素，直到找到目标元素或者遍历完整个数据结构。以下是C语言实现顺序查找的代码：

#include <stdio.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // 返回目标元素的索引
        }
    }
    return -1;  // 目标元素不存在，返回-1
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 3;
    
    int result = linearSearch(arr, n, target);
    
    if (result == -1) {
        printf("目标元素不存在\n");
    } else {
        printf("目标元素的索引是：%d\n", result);
    }
    
    return 0;
}

折半查找（Binary Search）是一种高效的查找算法，适用于有序的数据结构。它通过不断缩小查找范围的方式进行查找，每次将目标元素与查找范围中间的元素进行比较，从而将查找范围减半。以下是C语言实现折半查找的代码：

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;  // 返回目标元素的索引
        }
        
        if (arr[mid] < target) {
            left = mid + 1;  // 目标元素在右侧
        } else {
            right = mid - 1;  // 目标元素在左侧
        }
    }
    
    return -1;  // 目标元素不存在，返回-1
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 3;
    
    int result = binarySearch(arr, 0, n - 1, target);
    
    if (result == -1) {
        printf("目标元素不存在\n");
    } else {
        printf("目标元素的索引是：%d\n", result);
    }
    
    return 0;
}

以上就是顺序查找和折半查找的C代码实现。

编写顺序表的查找算法 编写折半查找算法 编写二叉排序树查找算法

顺序表的查找算法：

#include <stdio.h>

#define MAX_SIZE 10

int seq_search(int arr[], int n, int x)
{
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

int main()
{
    int arr[MAX_SIZE] = {3, 5, 7, 9, 11, 13, 15};
    int n = 7;
    int x = 9;
    int idx = seq_search(arr, n, x);
    if (idx != -1) {
        printf("%d is at index %d\n", x, idx);
    } else {
        printf("%d is not found\n", x);
    }
    return 0;
}

折半查找算法：

#include <stdio.h>

#define MAX_SIZE 10

int binary_search(int arr[], int n, int x)
{
    int l = 0;
    int r = n - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (arr[m] == x) {
            return m;
        } else if (arr[m] < x) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return -1;
}

int main()
{
    int arr[MAX_SIZE] = {3, 5, 7, 9, 11, 13, 15};
    int n = 7;
    int x = 9;
    int idx = binary_search(arr, n, x);
    if (idx != -1) {
        printf("%d is at index %d\n", x, idx);
    } else {
        printf("%d is not found\n", x);
    }
    return 0;
}

二叉排序树查找算法：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode *create_node(int val)
{
    struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct TreeNode *insert_node(struct TreeNode *root, int val)
{
    if (root == NULL) {
        return create_node(val);
    }
    if (val < root->val) {
        root->left = insert_node(root->left, val);
    } else if (val > root->val) {
        root->right = insert_node(root->right, val);
    }
    return root;
}

struct TreeNode *search_node(struct TreeNode *root, int val)
{
    if (root == NULL || root->val == val) {
        return root;
    }
    if (val < root->val) {
        return search_node(root->left, val);
    } else {
        return search_node(root->right, val);
    }
}

int main()
{
    int arr[] = {3, 5, 7, 9, 11, 13, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    struct TreeNode *root = NULL;
    for (int i = 0; i < n; i++) {
        root = insert_node(root, arr[i]);
    }
    int x = 9;
    struct TreeNode *node = search_node(root, x);
    if (node != NULL) {
        printf("%d is found\n", x);
    } else {
        printf("%d is not found\n", x);
    }
    return 0;
}