首页 > 代码库 > 浅谈顺序、折半查找
浅谈顺序、折半查找
线性表查找的实现原理
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]); }}
浅谈顺序、折半查找
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。