查找算法（第一弹）顺序查找和折半查找

顺序查找

算法描述

       顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。该算法的时间复杂度为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<arr.length;i++) { 12 if(arr[i]==n) { 13 return i; 14 } 15 } 16 return -1; 17 } 18 //返回包含所有下标的ArrayList集合 19 public static ArrayList<Integer> seqAllSearch(int[] arr,int n){ 20 ArrayList<Integer> arrlist=new ArrayList<Integer>(); 21 for(int i=0;i<arr.length;i++) { 22 if(arr[i]==n) { 23 arrlist.add(i); 24 } 25 } 26 return arrlist; 27 } 28 29 public static void main(String[] args) { 30 int[] arr= {1,3,3,5,7,8,8,8,8,9,10,123,134}; 31 int res=seqFirstSearch(arr, 8); 32 System.out.println("Index= "+res); 33 ArrayList<Integer> arrlist=seqAllSearch(arr, 8); 34 System.out.println(arrlist.toString()); 35 } 36 37 }

 

二分查找

算法描述：

　　二分查找（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<n) { 20 return binaryFirstSearch1(arr,mid+1,right,n); 21 }else{ 22 while(arr[mid]==n) { 23 mid--; 24 } 25 return mid+1; 26 } 27 } 28 public static ArrayList<Integer> binaryAllSearch(int[] arr,int n) { 29 int right=arr.length-1; 30 //ArrayList<Integer> arrlist=new ArrayList<Integer>(); 31 ArrayList<Integer> res=binaryAllSearch1(arr,0,right,n); 32 return res; 33 } 34 private static ArrayList<Integer> binaryAllSearch1(int[] arr,int left,int right,int n) { 35 if(left>right) { 36 return new ArrayList<Integer>(); 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<n) { 43 return binaryAllSearch1(arr,mid+1,right,n); 44 }else{ 45 ArrayList<Integer> arrlist=new ArrayList<Integer>(); 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<Integer> arrlist=binaryAllSearch(arr, 8); 62 System.out.println(res); 63 System.out.println(arrlist.toString()); 64 } 65 66 }

 

复杂度分析 

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

 

 

转载于:https://www.cnblogs.com/fangtingfei/p/11545572.html