顺序查找

算法描述

       顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。该算法的时间复杂度为O(n)。

       顺序查找是从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。

优缺点

    缺点：是当n 很大时，平均查找长度较大，效率低；

    优点：是对表中数据元素的存储没有要求，可以是无序的。另外，对于线性链表，只能进行顺序查找。

我的代码实现（包含返回首值和返回所有值的数组两种方法）：

1 package cn.ftf.mysearch; 2  3 import java.util.ArrayList; 4  5 /* 6  * 线性查找 7  */ 8 public class MySeqSearch { 9     //只返回第一个的下标10     public static int seqFirstSearch(int[] arr,int n) {11         for(int i=0;i
     
       seqAllSearch(int[] arr,int n){20         ArrayList
      
        arrlist=new ArrayList
       
        ();21         for(int i=0;i
       
      
     

 

二分查找

算法描述：

　　二分查找（Binary Search），是一种在有序数组中查找某一特定元素的查找算法。查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

　　这种查找算法每一次比较都使查找范围缩小一半。

 

我的代码实现(包含返回首值和返回所有值的数组两种方法)：

 

1 package cn.ftf.mysearch; 2  3 import java.util.ArrayList; 4  5 public class MyBinarySearch { 6     public static int binaryFirstSearch(int[] arr,int n) { 7         int right=arr.length-1; 8         int res=binaryFirstSearch1(arr,0,right,n); 9         return res;10     }11     private static int binaryFirstSearch1(int[] arr,int left,int right,int n) {12         if(left>right) {13             return -1;14         }15         int mid=(left+right)/2;16         int midValue=arr[mid];17         if(midValue>n) {18             return binaryFirstSearch1(arr,left,mid-1,n);19         }else if(midValue
     
       binaryAllSearch(int[] arr,int n) {29         int right=arr.length-1;30         //ArrayList
      
        arrlist=new ArrayList
       
        ();31         ArrayList
        
          res=binaryAllSearch1(arr,0,right,n);32         return res;33     }34     private static ArrayList
         
           binaryAllSearch1(int[] arr,int left,int right,int n) {35         if(left>right) {36             return new ArrayList
          
           ();37 }38 int mid=(left+right)/2;39 int midValue=arr[mid];40 if(midValue>n) {41 return binaryAllSearch1(arr,left,mid-1,n);42 }else if(midValue
           
             arrlist=new ArrayList
            
             ();46 while(arr[mid]==n) {47 mid--;48 }49 int firstIndex=mid+1;50 while(arr[firstIndex]==n) {51 arrlist.add(firstIndex);52 firstIndex++;53 }54 return arrlist;55 }56 } 57 58 public static void main(String[] args) {59 int[] arr= {1,3,3,5,7,8,8,8,8,9,10,123,134};60 int res=binaryFirstSearch(arr,8);61 ArrayList
             
               arrlist=binaryAllSearch(arr, 8);62 System.out.println(res);63 System.out.println(arrlist.toString());64 }65 66 }
             
            
           
          
         
        
       
      
     

 

复杂度分析 

    时间复杂度：折半搜索每次把搜索区域减少一半，时间复杂度为 O(logn)

    空间复杂度：O(1)