一、二分法查找的适用条件？

二分法查找是一种效率比较高的查找方法，在进行二分法查找时，线性表节点必须按关键码值排序，且 线性表是以顺序存储方式存储的。 二分法查找的优点是比较次数少，查找速度快，平均检索长度小，经过｛＿loge n次比较就可以完成查找过程。缺点是在查找之前要为建立有序表付出代价，同时对有序表的插人和删除都需要平均比较和移动表中 的一半元素。一般情况下，二分查找适应于数据相对固定的情况，且二分法查找只适用于线性表的顺序存储。

二、pdl二分查找算法？

pdl二分查找充分利用了序列元素的递增性质，采用分治策略搜索目标值（目标值存在于序列中），目标值的左边界和右边界（目标值不存在于序列中），其中左边界指的是最大的小于目标值的元素，右边界指的是最小的大于目标值的元素。

三、折半查找的适用条件？

适用的前提条件：

1. 存储在数组中（例如一维数组）

2. 数组元素为有序（例如升序）查找的基本思想：折半查找，设查找的元素为value value与中间元素（middle = left + (right -left) / 2这样做的好处防止中间元素出现越界）比较，若比中间值小则查找范围在middle + 1继续查找，若比中间值大则查找范围在middle -1,若与中间值相等则查找结束索引元素为value = middle。

四、二分查找法适用的前提条件？其查找的基本思想？

适用的前提条件：

1. 存储在数组中（例如一维数组）

2. 数组元素为有序（例如升序） 查找的基本思想：折半查找，设查找的元素为value value与中间元素（middle = left + (right -left) / 2这样做的好处防止中间元素出现越界）比较，若比中间值小则查找范围在middle + 1继续查找，若比中间值大则查找范围在middle -1,若与中间值相等则查找结束索引元素为value = middle。

五、二分查找算法遇到小数怎么办？

如果是下标之和除以2得到的小数，这个直接下取整，也就是去掉那个0.5

六、二分查找算法 时间和大小有关系吗？

二分查找本来就是针对排好序的数据说的，复杂度是O(logn)；

如果是未排序的数据，查找一次，显然最快的只能挨个查一遍，时间复杂度是O(n)；

如果是多次查找，排序的工作量（快排是O(nlogn))被均摊，查找次数越多越划算

七、在一个有序数列中查找，二分查找是最优算法吗？

二分查找时间复杂度是O(log2n)，如果一次比较可以做到k等分（也就是排除掉k-1个其他相同长度），时间复杂度为O(logkn)，复杂度的数量级一致，但是，运算量小一些，其实那个b树就是这个思想

八、prime算法的查找规则？

Prime算法：是一种穷举查找算法来从一个连通图中构造一棵最小生成树。利用始终找到与当前树中节点权重最小的边，找到节点，加到最小生成树的节点集合中，直至所有节点都包括其中，这样就构成了一棵最小生成树。prime在算法中属于贪心算法的一种，贪心算法还有：Kruskal、Dijkstra以及哈夫曼树及编码算法。

九、顺序查找和折半查找的算法心得？

1.顺序查找:<适合对象——无序或有序队列>

思想:逐个比较,直到找到或者查找失败。

时间复杂度:T(n) = O(n)。

2.折半查找:<适合对象——只是适用于有序表,且限于顺序存储结构(线性链表无法进行折半查找)>

思想:又称二分查找,对于已经按照一定顺序排列好的列表,每次都用关键字和中间的元素...

时间复杂度:T(n) =O(logn)。

十、什么算法适用于对于分布式存储的数据的查找？

在分布式存储解决方案中，当客户需要访问某块数据时（通过对象的id或者文件的路径及偏移量），首先要做的就是定位数据保存在哪一台服务器上。有两种做法，一种是单独指定一台或几台服务器来管理数据的位置映射，另一种是通过某种精巧设计的算法使用对象的id或者文件的路径及偏移量直接计算出位置。

第一种方法虽然容易想到并且实现简单，比如hdfs的namenode，swift的proxy node，但是缺点也很明显，一个是单点故障问题，必须使用HA或者loadbalancer来保证足够的安全以及分流请求。

现实中数据的存储要保证安全性，所以一定要有备份，非常重要的一般是三份，普通数据也可以配置成两份，为了节省空间并不失安全性，还可以采用EC(Erasure Coding)，但是EC的计算量大一些，如果存储节点的CPU有空闲，可以考虑一下。另外出于安全性考虑，备份一般有个规则，同一份数据的不同备份往往存在不同机架上，使用了EC之后，为了安全性，EC的数据最好要分布到不同机架上。

另外分布式存储非常看重的是横向扩展性，也就是节点的自动增减。这又有两种做法，一是原有数据不懂，只把新的数据存储到放到新增节点上；另一种方法是对原有数据重新分布，这就必然要修改数据到物理存储的映射关系。现在的存储方案为了考虑磁盘使用的平均化，往往对原有数据做重新分布，如果实现的不够好，很可能导致存储节点间数据流量过大，对外访问的一致性和性能变差，甚至系统变得不可用。

Swift的一致性Hash算法

Swift提供的是对象接口，对象数据定位的算法是这样的：

1. 对所有对象的名字做hash，hash之后的数值取0-2^n，将hash空间首尾相连形成一个环

2. 每个存储device也被分配不同的hash值，并且均匀分布在hash环上。（后来为了减少增减设备引起的数据迁移造成的不平衡，每个device被分配多个虚拟的hash值，不同device的虚拟hash值交错分布）

3. 当有对象写入时，计算这个对象的hash值，从hash环上对应位置开始向前寻找，找到的第一个device即为该对象的存储位置。

4. 当有device增减时，原有的device的hash值保持不变，但邻近的device需要进行数据迁移，以保证数据的可访问性。