顺序查找
顺序查找又称线性查找。它的过程为:从查找表的第一个元素开始逐个与给定关键字比较,
若某个记录的关键字和给定值比较相等,则查找成功,否则,若直至最后一个记录,其关键字和给定值比较都不等,
则表明表中没有所查记录查找不成功,它的缺点是效率低下。
代码:
1 public static void orderSearch(int[] arr, int value) { 2 for (int i = 0; i < arr.length; i++) { 3 if (arr[i] == value) { 4 System.out.println(value + "的索引值是" + i); 5 } 6 } 7 }
二分查找
二分查找又称折半查找,必须为有序表,它的优点是比较次数少,查找速度快,平均性能好。
二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x。
二分查找的时间复杂度为O(logn)
代码:
1 public static int funBinSearch(int[] arr, int data) { 2 int low = 0; 3 int high = arr.length - 1; 4 while (low <= high) { 5 int mid = (low + high) / 2; 6 if (data == arr[mid]) { 7 return mid; 8 } else if (data < arr[mid]) { 9 high = mid - 1; 10 } else if (data > arr[mid]) { 11 low = mid + 1; 12 } 13 } 14 return -1; 15 }