数据结构-顺序查找和折半查找

梦里梦外; 2022-05-13 13:08 224阅读 0赞

顺序查找即线性查找，通常分为一般无序线性表的顺序查找和有序顺序表的顺序查找。  
一般线性表的顺序查找：从线性表的一端开始，逐个检查关键字是否满足条件，若存在则查找成功，返回线性表的位置；否则查找失败。  
有序表顺序查找：即查找之前就已知顺序表是排序了的。假设线性表L是按关键字从小到大排列的，查找的顺序是从前往后查找，待查找元素的关键字为key,  
当查找到第i个元素时，发现第i个元素对应的关键字小于key,但第i+1个元素的关键字均大于key，所以表中不存在关键字为key的元素。

折半查找：又称为二分法查找，仅适用于有序的顺序表。基本思路为：首先将给定值key与表中中间位置元素的关键字比较，若相等，则查找成功，返回元素位置，  
若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中（例如：若升序表中，给定的key大于中间元素的关键字，则所查找的元素只可能在后半部分）。

然后缩小范围继续进行同样的查找，如此重复直至找到为止，或者查找失败。

//
    // Created by Administrator on 2018/7/6.
    //
    #include "stdio.h"
    
    
    /**
     * 顺序查找法1
     * @param str
     * @param n
     * @param key
     * @return
     */
    int search1(int str[], int n, int key) {
        for (int i = 0; i < n; ++i) {
            if (str[i] == key) {
                return i;
            }
        }
        return -1;
    }
    
    /**
     * 顺序查找法 （哨兵模式：0号单元留空）
     * @param str
     * @param n
     * @param key
     * @return
     */
    /*int search2(int str[], int n, int key) {
        str[0] = key;
        while (str[n] != key) {
            n--;
        }
        return n;
    }*/
    
    
    /**
     * 折半查找法
     * @param str
     * @param len
     * @param key
     * @return
     */
    int halfSearch(int str[], int len, int key) {
        int low, high, mid;
        low = 0;
        high = len - 1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (str[mid] == key) {
                return mid;
            } else if (str[mid] < key) {
                //right
                low = mid + 1;
            } else if (str[mid] > key) {
                //left
                high = mid - 1;
            }
        }
        return -1;
    }
    
    /**
     * 插值法（按比例查找：经测试 存在局限性）
     * @param str
     * @param len
     * @param key
     * @return
     */
    /*int precentSearch(int str[], int len, int key) {
        int low, high, mid;
        low = 0;
        high = len - 1;
        while (low <= high) {
            mid = low + (key - str[low] / str[high] - str[low]) * (high - low); // 插值查找的唯一不同点
            if (str[mid] == key) {
                return mid;
            } else if (str[mid] < key) {
                //right
                low = mid + 1;
            } else if (str[mid] > key) {
                //left
                high = mid - 1;
            }
        }
        return -1;
    }*/
    
    int main() {
        int str[9] = {1, 1, 2, 3, 5, 8, 13, 21, 34};
        int key = 3;
        int i;
    //    i = precentSearch(str, 9, key);
    //    printf("按比例查找法查找到关键字 %d 的位置为 %d \n", key, i);
        i = search1(str, 9, key);
        printf("顺序查找法1查找到关键字 %d 的位置为 %d \n", key, i);
    //    i = search2(str, 9, key);
    //    printf("顺序查找法2查找到关键字 %d 的位置为 %d \n", key, i);
        i = halfSearch(str, 9, key);
        printf("折半查找法查找到关键字 %d 的位置为 %d \n", key, i);
        return 0;
    }

![70][]

[70]: /images/20220504/11bc22a7d9844c83b9d729763c222d2d.png