二分法查找和普通查找

一、普通查找

  对于数组和一个需要查找的元素来说，普通查找的原理很简单，即为从数组的第一个元素到最后一个元素进行遍历，如果第i个元素的值等于我们需要查找的值，那么返回找到的角标i，否则返回-1表示没有查找到。这里以java为例，普通查找代码如下：

1 package Daily_practice; 2 3 public class Array_Search { 4 5 public static void main(String[] args) { 6 int[] arr1 = {33,19,15,28,106,45,78,13}; 7 //普通查找 8 int index1 = getIndex(arr1,28); 9 System.out.println(index1); 10 } 11 //普通查找,返回值所在的角标，不存在返回-1 12 public static int getIndex(int[] arr,int value) 13 //value为需要查找的值 14 { 15 for(int i=0;i<arr.length;i++) 16 { 17 if(arr[i] == value) 18 return i; 19 } 20 return -1; 21 } 22 }

二、二分法查找

  二分法是从中间元素开始查找，假设整型数组为arr，要查找的元素为value，数组中间元素为arr[mid]，若value小于arr[mid],则在左半边继续查找；若value大于arr[mid],则在右半边继续查找，如此循环，知道value等于arr[mid]，返回的角标mid即为要找的元素的位置。java代码如下：

1 package Daily_practice; 2 3 public class Array_Search1 { 4 5 public static void main(String[] args) { 6 int[] arr2 = {13,15,19,28,33,45,78,106}; 7 //二分法查找 8 int index2 = halfSearch(arr2,28); 9 System.out.println(index2); 10 } 11 12 //二分法查找 13 public static int halfSearch(int[] arr,int value) 14 { 15 int min,mid,max; 16 min = 0; 17 max = arr.length-1; 18 mid = (min+max)/2; 19 while(arr[mid] != value) 20 { 21 if(value > arr[mid]) 22 min = mid + 1; 23 else 24 max = mid - 1; 25 if(max < min) 26 return -1; 27 mid = (min+max)/2; 28 } 29 return mid; 30 } 31 32 }

三、二分法查找和普通查找的优缺点分析

  •普通查找

  优点：1）原理简单，代码容易实现

        2）不需要数组有序

  缺点：1）当元素个数很多时，效率较低

 

  •二分法查找

  优点：1）效率比普通查找高

  缺点：1）要求数组必须是有序排列

四、总结

  两种方法各有优点和局限，至于具体用哪一种请读者根据实际情况而定，文中若有不恰当之处请批评指正！