带有哨兵的顺序表查找和二分法查找（折半查找）（java）代码+说明

一：带有哨兵的顺序表查找

1、算法设计：

* 在一个线性表中，按照从前往后或者从后往前的顺序依次查找，如果查找到关键字和给定值相等，则返回给定值的位置，查找成功；

* 如果查找值最后一个元素仍未找到，则查找失败。

* 带哨兵的顺序查找,所谓哨兵就是将关键字用一个数组位置去存储，保证在循环的过程中不必判断数组是否越界，因为执行到最后一个元素时，

* 一定会跳出循环。在一定程度上优化了普通查找算法

2、 源代码：

public void search_Sq(E e) {int i;data[0] = e;for(i=size;!data[i].equals(e);i--);if(i == 0)System.out.println("没有找到该数据");elseSystem.out.println("成功找到该数据"+data[i]);}

二、二分法查找（折半查找）

1、算法设计：

* 二分查找，所针对的是有序数组，即数据在之前必须已经由小到大排序完成。

* 通过寻找中间数并比较大小，确定目标数所在区间，并且不断通过这种方法缩小区间，直到找到目标数。

* 具体实现如下：

*

* 1. 通过数组容量size确定上(high)下(low)边界，计算得出中间数位置(mid)。

*

* 2. 比较mid处的数与目标数e的大小，确定目标数所在区间(左半部分或右半部分或者该处就是e)。

*

* 3. (1)若X在左半部分，则将上界high左移到mid的左边。再重新确定mid，重复1，2步骤。

*

* (2)若X在右半部分，则将下界low左移到mid的右边。再重新确定mid，重复1，2步骤。

*

* (3)若X即为mid处的数，则返回mid的值。

2、源代码：

public void search_Bin(E e) {int low,high,mid;low = 1;high = size;while(low <=high) {mid = (low + high)/2;if(data[mid].compareTo(e)>0)high = mid -1;else if(data[mid].compareTo(e)<0)low = mid+1;else { System.out.println("成功找到数据"+data[mid]);return ;}}

三、下面为全文源代码，供各位调试数据使用

package com.atguigu.tree;import java.util.Scanner;public class OrderSqList<E extends Comparable <E>> {private E[ ] data;//0号单元不存放元素private int size;//构造函数，传入数组容量构造Arraypublic OrderSqList(int capacity){data =(E[]) new Comparable[capacity];size=0;}//无参构造函数，默认数组容量为10public OrderSqList() {this(10);}public int getsize() {return size;}public int getCapacity() {return data.length;}public boolean isEmpty() {return size==0;}public void add(E e) {//判断数组是否已满if(size==data.length)throw new IllegalArgumentException("Add Faild,List is full.");//移动元素，腾出位置int cur=size;while(cur>=1&&pareTo(data[cur])<0) {data[cur+1]=data[cur];cur--;}//将e插入到cur+1位置data[cur+1]=e;//维护sizesize++;}public E get(int index) {if(index<=0 || index>size)throw new IllegalArgumentException("Get Faild,Index is illegal.");return data[index];}public boolean contains(E e) {for(int i=1;i<=size&&data[i].compareTo(e)<=0;i++)if(data[i].equals(e ))return true;return false;}//按关键字查找//查找数组中元素e所在的索引，如果e不存在，则返回0；public int find(E e) {int i;for(i=1;i<=size&&data[i].compareTo(e)<0;i++);if(i<size && data[i].equals(e))return i;return 0;} //普通的顺序查找public int search(E e) {int i;for(i=size;i>=1&&!data[i].equals(e);i--);return i;}//带哨兵的顺序查找/** 在一个线性表中，按照从前往后或者从后往前的顺序依次查找，如果查找到关键字和给定值相等，则返回给定值的位置，查找成功；* 如果查找值最后一个元素仍未找到，则查找失败。* 带哨兵的顺序查找,所谓哨兵就是将关键字用一个数组位置去存储，保证在循环的过程中不必判断数组是否越界，因为执行到最后一个元素时，* 一定会跳出循环。在一定程度上优化了普通查找算法*/public void search_Sq(E e) {int i;data[0] = e;for(i=size;!data[i].equals(e);i--);if(i == 0)System.out.println("没有找到该数据");elseSystem.out.println("成功找到该数据"+data[i]);}//折半查找/** 二分查找，所针对的是有序数组，即数据在之前必须已经由小到大排序完成。* 通过寻找中间数并比较大小，确定目标数所在区间，并且不断通过这种方法缩小区间，直到找到目标数。* 具体实现如下：* * 1. 通过数组容量size确定上(high)下(low)边界，计算得出中间数位置(mid)。* * 2. 比较mid处的数与目标数e的大小，确定目标数所在区间(左半部分或右半部分或者该处就是e)。* * 3. (1)若X在左半部分，则将上界high左移到mid的左边。再重新确定mid，重复1，2步骤。* * (2)若X在右半部分，则将下界low左移到mid的右边。再重新确定mid，重复1，2步骤。* * (3)若X即为mid处的数，则返回mid的值。*/public void search_Bin(E e) {int low,high,mid;low = 1;high = size;while(low <=high) {mid = (low + high)/2;if(data[mid].compareTo(e)>0)high = mid -1;else if(data[mid].compareTo(e)<0)low = mid+1;else { System.out.println("成功找到数据"+data[mid]);return ;}}System.out.println("没有找到该数据");}public E remove(int index) {if(index<=0||index>size)throw new IllegalArgumentException("Remove Faild,Index is illegal.");E ret=data[index];for(int i=index;i<=size-1;i++)data[i]=data[i+1];size--;data[size]=null;return ret;}public E removeFirst() {return remove(1);}//删除数组中的元素epublic void removeElement(E e){int index=find(e);if(index==0)throw new IllegalArgumentException(String.format("Remove Faild,%d is not exist.",e));remove(index);}@Overridepublic String toString() {StringBuilder res=new StringBuilder();res.append(String.format("Array:size=%d,capacity=%d\n",size,data.length));res.append('[');for(int i=1;i<=size;i++) {res.append(data[i]);if(i!=size)res.append(",");//元素之间用逗号分隔}res.append(']');return res.toString();}public static void main(String[] args) {OrderSqList<Integer> arr1 = new OrderSqList<>();char key = ' '; //接收用户输入Scanner scanner = new Scanner(System.in);//boolean loop = true;//输出一个菜单while(loop) {System.out.println("s(show): 显示队列");System.out.println("e(exit): 退出程序");System.out.println("a(add): 添加数据");System.out.println("g(get): 查找数据（顺序表）");System.out.println("h(head): 查找数据（二分法）");key = scanner.next().charAt(0);//接收一个字符switch (key) {case 'a':System.out.println("输入添加的数据");int value = scanner.nextInt();arr1.add(value);break;case 's':System.out.println(arr1);break;case 'g':System.out.println("输入想要查找的数据");int value1 = scanner.nextInt();arr1.search_Sq(value1);break;case 'h':System.out.println("输入想要查找的数据");int value2 = scanner.nextInt();arr1.search_Bin(value2);break;case 'e': //退出scanner.close();loop = false;break;default:break;}}System.out.println("程序退出~~");}}

以上内容参考自其它博主加网络资源汇编。