查找方法總結---待完善

myFind.h

#ifndef MYFIND_H_INCLUDED
#define MYFIND_H_INCLUDED

/*
線性查找：順序查找\折半查找
兩種形式：破壞性查找\非破壞性查找
*/

//順序查找:如果查找的到就返回key在數組中第一個位置的下標，否則返回-1
int sequenceSearc(int arr[], int arrLen, int key);

//折半查找：數組必須有序、只限于線性查找
int binarySearch(int arr[], int arrLen, int key);

/*
哈希查找：key-valus通過哈希函數建立一種關系，能夠做到O(1)。
key要盡可能的分散，最好能保證每個key都有一個相應的value，同時哈希函數也要盡可能簡單快速
哈希函數：直接定址法、除法取余法、數字分析法、平方取中法、折疊法
解決沖突的方法：開放地址法、鏈接法
*/

/*
索引查找：
索引:就是把一個關鍵字與它對應的i記錄相關聯的過程，一個索引由若干個索引項構成，每個索引項至少應包含關鍵字和其對應的記錄在存儲器中的位置等信息。
索引按照結構可以分為：線性索引、樹形索引和多級索引。
線性索引是將索引項集合組織為線性結構，也稱為索引表。包括稠密索引、分塊索引、倒排索引。
*/

/*
二叉排序樹：根節點的左孩子小于根節點，根節點的右孩子大于根節點（相同數字？？）

*/

#endif // MYFIND_H_INCLUDED

myFind.c

#include "myFind.h"
#include "mysort.h"

//線性查找：O(n)
int sequenceSearc(int arr[], int arrLen, int key)
{
    int i;

    for (i = 0; i < arrLen; i++)
    {
        if (key == arr[i])
        {
            return i;
        }
    }

    return -1;
}

//折半無序(使用最快的排序方法)：O(NlogN)+O(logN);折半有序的時間復雜度：O(logN);
int binarySearch(int arr[], int arrLen, int key)
{
    int left;
    int right;
    int middle;

    //先排序
    quickSort(arr, 0, arrLen - 1);

    left = 0;
    right = arrLen - 1;

    while (left <= right)
    {
        middle = (left + right) / 2;

        if (key == arr[middle])     //如果key恰好等于中間數字就返回
        {
            return middle;
        }
        else if (key < arr[middle]) //key小于中間值，則向左查找
        {
            right = middle - 1;
        }
        else
        {
            left = middle + 1;
        }
    }

    return -1;
}