浅谈顺序、折半查找

线性表查找的实现原理

　　1、线性表查找：顺序查找、折半查找。

　　2、顺序查找的实现思想

　　　　遍历全表，判断值是否相等，俗称蛮力法。

　　3、折半查找

　　　　步骤一：设置初始查找取件：left=0；right=n；

　　　　步骤二：测试查找区间[left,right]是否存在，若不存在，则查找失败，否则

　　　　步骤三：取中间位置mid=(left+right)/2；比较target与array[mid]，有三种情况

　　　　　　　　　　若target<array[mid]，right=mid-1;查找在mid左半区继续进行，返回步骤二

　　　　　　　　　　若target>array[mid]，left=mid+1；查找在mid右半区继续进行，返回步骤二

　　　　　　　　　　若target=array[mid]，则查找成功，返回记录在表中的位置mid。

顺序查找的代码实现

public class SequenceList {
    //数组的蛮力查找
    public static int sequentialSearch(int [] array,int target){
        int length=array.length-1;
        while(array[length]!=target&&length>=0)
            length--;
        if(array[length]==target)
            return length;
        return -1;
    }
    
    //单链表的蛮力查找
    public static int sequetialSearchByLinkedList(Node first,int target){
        if(null==first)
            return -1;
        int count=0;
        Node p=first;
        while(p.getData()!=target){
            count++;
            p=p.getNext();
        }
        if(p.getData()==target)
            return count;
        return -1;
    }
    
}

折半查找的代码实现

 

public class SequenceList {
    public static int binarySearch(int [] array,int target){
        if(array==null||array.length<0){
            return -1;
        }
        int left=0;
        int right=array.length;
        while(left<=right){
            int mid=(left+right)/2;
            if(target>array[mid]){
                left=mid+1;
            }else if(target<array[mid]){
                right=mid-1;
            }else{
                return mid;
            }    
        }
        return -1;
    }
    
    public static int recursiveBinarySearch(int [] array,int target,int left,int right){
        if(array==null||array.length<0){
            return -1;
        }
        if(left>right){
            return -1;
        }else{
            int mid=(left+right)/2;
            if(target<array[mid]){
                return recursiveBinarySearch(array, target, left, mid-1);
            }else if(target>array[mid]){
                return recursiveBinarySearch(array, target, mid+1, right);
            }else{
                return mid;
            }
        }
    }
    
    public static void main(String[] args) {
        int [] array=new int[]{7,14,18,21,23,29,31,35,38,42,46,49,52};
        
        Arrays.sort(array);
        int j=SequenceList.binarySearch(array,11);
        System.out.println(array[j]);
        
        int k=SequenceList.recursiveBinarySearch(array, 66,0,array.length);
        System.out.println(array[k]);
    }
}