一、顺序查找
顺序查找：
从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直值第一个记录，其关键字和给定值比较都不想等，则表明表中没有所查记录，查找失败。
代码实现：
#include <stdio.h> #include <stdlib.h> typedef int ElemType; #define EQ(a, b) ((a)==(b)) int sequential(int array[], ElemType key, int n) { int index; for(index = 0; index < n; index++){ if(EQ(array[index],key)) return index + 1; } return -1; } int main(void) { ElemType array[] = {1, 4, 5, 2, 7, 8, 3}; int length = sizeof(array); printf("the index you search is %d.\n", sequential(array, 5, length)); return 0; }
备注：查找速度慢，平均查找长度为 (n + 1) / 2，时间复杂度为 O(n) 。
二、二分查找（折半查找）
折半查找：
首先需要要查找的序列是有序的（下面的讨论基于递增有序）。
假设Array[start , ... , end]为当前的查找区间，首先确定该区间的中间位置，即mid = (start + end) / 2;
然后将待查找的k值与Array[mid]做比较，此时有三种情况：
第一，若k = Array[mid]。则查找成功，返回mid即为查找到的位置；
第二，若k > Array[mid]。则说明k值在Array序列的右半边，此时的查找序列将变为Array[mid+1, ... , end]；
第三，若k < Array[mid]。则说明k值在Array序列的左半边，此时的查找序列将变为Array[start, ... , mid-1]。
不断地递归进行下去，直到区间的长度小于1时查找结束。
代码实现：
public class BinaryFind { public BinaryFind() { // TODO Auto-generated constructor stub } public int binary_find_1(int array[],int start,int end,int k){ //折半查找的递归实现 int find_index = -1; //初始查找位置为-1，即代表查找失败 if (start <= end) { //如果区间长度大于等于1 int mid_index = (start + end)/2; //首先确定区间的中间位置 if (array[mid_index] == k) { //将要查找的k值与区间中间位置值进行比较 return mid_index; //k值与区间中间位置值相等，返回中间位置下标，查找成功 }else if(k > array[mid_index]){ //k值比中间位置值大，在右半边继续递归查找 return binary_find_1(array,mid_index+1,end,k); }else { //k值比中间位置值小，在左半边继续递归查找 return binary_find_1(array,start,mid_index-1,k); } } return find_index; } public int binary_find_2(int array[],int start,int end,int k){ //折半查找的循环实现 int find_index = -1; while (start <= end) { int mid_index = (start + end)/2; if (array[mid_index] == k) { return mid_index; }else if(k > array[mid_index]){ start = mid_index + 1; }else { end = mid_index - 1; } } return find_index; } public static void main(String[] args) { int[] array = {1,2,3,4,5,6,7,8,9,10}; BinaryFind binaryFind = new BinaryFind(); System.out.println(""+binaryFind.binary_find_2(array,0,9,5)); } }
备注：对于有n个记录的查找便进行折半查找的时间复杂度为O(logn)。
