java线性查找、二分查找(2015年9月23日)

r囧r小猫 2022-08-08 19:31 155阅读 0赞

线性查找：

定义：在一列给定的值中进行搜索，从一端开始逐一检查每个元素，直到找到所需元素的过程。  
线性查找又称为顺序查找。如果查找池是某种类型的一个表，比如一个数组，简单的查找方法是从表头开始，一次将每一个值与目标元素进行比较。最后，或者查找到目标，或者达到表尾，而目标不存在于组中，这个方法称为线性查找。

import java.util.Scanner;  
      
    public class SequentialSearch {  
        int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};  
        public SequentialSearch(){  
            System.out.println("请输入要查询的数字：");  
            Scanner input=new Scanner(System.in);  
            int input1=input.nextInt();  
            for(int i=0;i<a.length;i++){  
                if(a[i]==input1){  
                    System.out.println(input1+"的位置为："+i);  
                    break;  
                }  
                if(i==a.length-1)  
                    System.out.println("No Result!");  
            }  
        }   
    }

二分查找：

二分查找又称折半查找，它是一种效率较高的查找方法。

【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。

**所以说用折半查找时序列必须是有序的！**

【算法思想】首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。  
　　重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

import java.util.Arrays;
    public class BinarySearch {
        public int search(int[] number, int des) {   
            int low = 0;   
            int upper = number.length - 1;   
            while (low <= upper) {   
                int mid = (low + upper) / 2;   
                if (number[mid] < des)   
                    low = mid + 1;   
                else if (number[mid] > des)   
                    upper = mid - 1;   
                else  
                    return mid;   
            }   
            return -1;   
        }   
      
        public void print(int[] array, String warn) {   
            System.out.println(warn);   
            int length = array.length;   
            for (int i = 0; i < length; i++) {   
                System.out.print(array[i] + " ");   
            }   
            System.out.println();   
        }   
      
        public static void main(String[] args) {   
            int[] array = { 1, 4, 2, 6, 7, 3, 5, 9, 8 };   
            BinarySearch find = new BinarySearch();   
            find.print(array, "数组排序前的结果:");   
            Arrays.sort(array);// Arrays中的静态方法sort()对数组排序   
            find.print(array,"数组排序后的结果:");   
            int m = find.search(array, 6);   
            if (m != -1)   
                System.out.println("\n找到6的数值的索引:" + m);   
            else  
                System.out.println("\n找不到这个数");   
        }   
    }