查找的类型

171 阅读 0 评论 113 点赞

我是靠谱客的博主粗暴世界，这篇文章主要介绍查找的类型，现在分享给大家，希望可以做个参考。

1.无序线性查找
假设给定一个数组，其元素的排列顺序是未知的，数组中的元素无序，如果要查找某个元素，必须通过扫描整个数组才能实现

复制代码

1
2
3
4
5
6
7
8
9
int unSortedLineSearch(int[] a,int n,int data){
  for(int i = 0;i<n;i++){
    if(a[i] == data){
      return i;
    }
  }
  return -1;
}

2.排序/有序线性查找
如果数组的元素已经排序，则许多情况下都不需要扫描整个数组来判断元素是否在给定的数组中

复制代码

1
2
3
4
5
6
7
8
9
10
int sortedLineSearch(int[] a,int n,int data){
  for(int i = 0;i<n;i++){
    if(a[i] == data){
      return i;
    }else if(a[i]>data){
      return -1;
    }
  }
}

3.二分查找

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//迭代的二分查找
int binarySearch(int[] a,int n,int data){
  int low = 0;
  int high = n-1;
  while(low<=high){
    int mid = low + (high - low)/2;
    if(a[mid] == data){
      return mid;
    }else if(a[mid] > data){
      high = mid -1;
    }else{
      low = mid +1;
    }
  }
  return -1;
}

//递归的二分查找法
int binarySearch(int[] a,int low,int high,int data){
  int mid = low + (high - low)/2;
  if(a[mid] == data){
    return mid;
  }else if(a[mid] < data){
    return bibarySearch(a,mid+1,high,data);
  }else{
    return binarySearch(a,low,mid-1,data);
  }
  return -1;
}