数据结构与算法（第一章.搜索）

请记住，所用的搜索法都是基于数列是有序的，如果不是，还需要进一步排序才可计算。

一.二分搜索法

#include<stdio.h>
int binary_searching(int * arr,int target,int left,int right){
    int mid=left+right;
    if (arr[mid]==target){
        return mid;
    }
    if(arr[mid]>target){
        binary_searching(arr,target,left,mid-1);
    }
    else{
        binary_searching(arr,target,mid+1,right);
    }


}
int main(){
    int arr1[10]={3,4,5,2,8,1,0,3,76,477};
    int target1=8;int left=3;int right=477;
    
}

二.三分搜索

#include <stdio.h>

int ternarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid1 = l + (r - l) / 3;
        int mid2 = r - (r - l) / 3;

        // 如果元素存在于中间的间隔中
        if (arr[mid1] == x || arr[mid2] == x) {
            return mid1 + 1; // 返回元素的下标+1，因为返回的是数组下标，不是索引
        }

        // 如果元素小于中间的第一个间隔，则在左边的子数组中查找
        if (arr[mid1] > x) {
            return ternarySearch(arr, l, mid1 - 1, x);
        }

        // 如果元素大于中间的最后一个间隔，则在右边的子数组中查找
        if (arr[mid2] < x) {
            return ternarySearch(arr, mid2 + 1, r, x);
        }

        // 如果元素不存在于数组中，则返回-1
        return -1;
    }

    return -1; // 如果数组为空或查找范围为空，则返回-1
}

int main() {
    int arr[] = {2, 5, 7, 8, 12, 14, 19, 20};
    int n = sizeof(arr) / sizeof(arr[0]); // 获取数组长度
    int x = 8; // 要查找的元素
    int result = ternarySearch(arr, 0, n - 1, x); // 在数组中查找元素
    if (result == -1) {
        printf("Element is not present in array"); // 如果元素不存在于数组中，则输出错误信息
    } else {
        printf("Element is present at index %d", result); // 如果元素存在于数组中，则输出元素的下标
    }
    return 0;
}