算法之查找--常见查找算法及总结

查找在算法考察中也占了相当大的比例，考察内容也很多。

   我们这里主要关注给定一个数据在无序数组中查找该元素是否存在，无序数组中是否存在二个数的和等于该元素， 有序数组中查找该元素是否存在，数据重复有序数组中该元素第一次出现的位置，最后一次出现的位置，第一次大于该元素出现的位置。 另外一种查找是查找某一个数组中最大的值，最大的一些值， 第K大的值等等。 我们这里也按照时间复杂度的顺序进行说明。

     在无序数组中查找某元素是否存在：

        最简单的方法就是遍历法，时间复杂度是o(n）。这里就不举例了。

     无序数组中是否存在二个数的和等于该元素：

            这里采用散列表来来实现，散列值是数组的值，值是数组的下标。时间复杂度是o(1)

              

 

 

      有序数组中查找该元素是否存在，数据重复有序数组中该元素第一次出现的位置，最后一次出现的位置，第一次大于该元素出现的位置：

        这里采用二分查找的方法来实现，时间复杂度是o(logn)

         元素是否存在：

      

         

         第一次出现的位置：

          

          

       最后一次出现的位置：

          

         第一次大于该元素出现的位置：

            

  

    查找某一个数组中最大的值:

        这里就用到了排序算法，可以参见上一篇的文章。

  查找某一个数组中最大的10个值:

        这里也可以采用堆排序的算法来实现，因为堆排序是动态数据结构，实际应用场景广泛。