查找方法总结---待完善

#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

#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;
}