欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

面试常用查找算法

程序员文章站 2022-07-12 09:17:14
...

面试常用查找算法

代码

方面适应所有算法,都使用有序数组

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

// sequence search
int SequenceSearch(int* a, int value, int length) {
    int i;
    for (i = 0; i < length; i++) {
        if (*(a + i) == value) {
            return i;
        }
    }
    return -1;
}

// binary search        (sort)
int Binary_Search_rescur(int* a, int value, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high && *(a + mid) == value) {
        return mid;
    } else if (low < high && *(a + mid) > value) {
        Binary_Search(a, value, low, mid - 1);
    } else if (low < high && *(a + mid) < value) {
        Binary_Search(a, value, mid + 1, high);
    } else {
        return -1;
    }
}
int Binary_Search(int* a, int value, int length) {
    int left = 0;
    int right = length;
    while (left <= right) {
        int mid = (left + right)/2;
        if (*(a + mid) == value) {
            return mid;
        } else if (*(a + mid) < value) {
            left = mid + 1;
        }
        else if (*(a + mid) > value) {
            right = mid - 1;
        }
    }
    return -1;
}

// insert search     (sort)
int Insert_Search(int* a, int value, int length) {
    int left = 0;
    int right = length;
    while (left <= right) {
        int mid = left + (value - *(a + left))/(*(a + right) - *(a + left)) * (right - left);
        if (*(a + mid) == value) {
            return mid;
        } else if (*(a + mid) < value) {
            left = mid + 1;
        } else if (*(a + mid) > value) {
            right = mid - 1;
        }
    }
    return -1;
}

// fibonacci search
void Make_Fib(int* fib, int size) {
    *fib = 1;
    *(fib + 1) = 1;
    int i;
    for (i = 2; i < size; i++) {
        *(fib + i) = *(fib + i - 1) + *(fib + i - 2);
    }
}
int Fibonacci_Search(int* a, int value, int length, int fib_size) {
    int left = 0;
    int right = length;
    int fib[fib_size];
    Make_Fib(fib, fib_size);
    int k = 0, i;
    while (right > *(fib + k)) {
        k++;
    }
    for (i = length + 1; i < *(fib + k); i++) {
        *(a + i) = *(a + length);
    }
    while (left <= right) {
        int mid = left + *(fib + k - 1) - 1;
        if (*(a + mid) == value) {
            if (mid <= length) {
                return mid;
            } else {
                return length;
            }
        } else if (*(a + mid) < value) {
            left = mid + 1;
            k -= 2;
        } else if (*(a + mid) > value) {
            right = mid - 1;
            k -= 1;
        }
    }
    return -1;
}

int main()
{
    int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int len = 10, num = 100, val, i;
    int fibn = 10;     // args for fibonacci array
    printf("a[10] = ");
    for (i = 0; i < 10; i++) {
        printf("%d ", *(a + i));
    }
    printf ("\nenter value : ");
    scanf("%d", &val);

    //num = SequenceSearch(a, val, len);
    //num = Binary_Search_rescur(a, val, 0, len - 1);
    //num = Binary_Search(a, val, len - 1);
    //num = Insert_Search(a, val, len - 1);
    num = Fibonacci_Search(a, val, len - 1, fibn);

    printf("value %d is num %d\n", val, num + 1);
    return 0;
}

相关标签: 查找