myFind.h

創(chuàng)新互聯(lián)公司總部坐落于成都市區(qū)，致力網(wǎng)站建設(shè)服務(wù)有成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站、網(wǎng)絡(luò)營銷策劃、網(wǎng)頁設(shè)計(jì)、網(wǎng)站維護(hù)、公眾號搭建、小程序設(shè)計(jì)、軟件開發(fā)等為企業(yè)提供一整套的信息化建設(shè)解決方案。創(chuàng)造真正意義上的網(wǎng)站建設(shè)，為互聯(lián)網(wǎng)品牌在互動行銷領(lǐng)域創(chuàng)造價(jià)值而不懈努力！

#ifndef MYFIND_H_INCLUDED
#define MYFIND_H_INCLUDED

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

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

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

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

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

/*
二叉排序樹：根節(jié)點(diǎn)的左孩子小于根節(jié)點(diǎn)，根節(jié)點(diǎn)的右孩子大于根節(jié)點(diǎn)（相同數(shù)字？？）

*/

#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);折半有序的時(shí)間復(fù)雜度：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恰好等于中間數(shù)字就返回
        {
            return middle;
        }
        else if (key < arr[middle]) //key小于中間值，則向左查找
        {
            right = middle - 1;
        }
        else
        {
            left = middle + 1;
        }
    }

    return -1;
}