折半查找算法

简介: 我们常常需要对数据进行查找,修改,查找数据有许多方法,我们先看看最简单的顺序查找

我们常常需要对数据进行查找,修改,查找数据有许多方法,我们先看看最简单的顺序查找


int main()
{
  int i, k = 0;
  scanf("%d", &k);
  int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  for (i = 0; i < sz; i++)
  {
  if (arr[i] == k)
  {
    printf("找到了,它是%d", arr[i]);
  }
  }
  return 0;
}


   1.如何判断查找完成,定义返回值含义,定义退出循环条件


   2.如何处理边界问题,例如1 2 3 这个序列,当我们要查找1或者3时,会不会使程序出现BUG


   3.对于数列来说,我们通常用整形存储其下标,二分查找若取下标中间数,则会出现什么样的问题?这些问题是否会影响我们的查找,若有问题,则应该如何规避?


   通常情况,作为一个初学者,我甚至觉得二分查找过于简单,不值一提,最近经过思考,二分查找算法对于理论的要求并不是很高,但是若要把它变为有可行性的程序代码,则我们需要思考诸多的细节,否则这个代码写出来则是错误百出的。


   如何解决第一个问题,因为我们了解的二分查找的思路其实就是折半查找,要有左边界与右边界我们才能确定中间元素,当左边界与右边界重合的时候,这时查找对象就变为一个元素的,若它也不是索要查找的对象,那么在所查找的集合中便没有所需的元素。这样我们就清楚地定义出来了所需参数,以及退出查找的条件。我们需要一个左边界以及右边界,还有中间元素,若右边界比左边界小(左比右大)时,退出循环,返回异常。若否,则执行 查找语句。

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<Windows.h>
int bin_search(int arr[], int left, int right, int key)
{
  int mid = 0;
  while (left <= right) 
  {
    mid = (left + right);
    if (arr[mid] > key)
    {
      right = mid - 1;
    }
    else if (arr[mid] < key)
    {
      left = mid + 1;
    }
    else
      return mid;
  }
  return -1;
}
int main()
{
  int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
  int left = 0;
  int right = sizeof(arr) / sizeof(arr[0]) - 1;
  int key = 7;
  int mid = 0;
  while (left <= right)
  {
    mid = (left + right) / 2;
    if (arr[mid] < key)
      left = mid + 1;
    else if (arr[mid] > key)
      right = mid - 1;
    else
      break;
  }
  if (right < left)
    printf("找不到\n");
  else
    printf("找到了,下标为:%d", mid);
}

二分查找:  

在一个有序的序列中,找某个数据是否在该集合中,如果在打印该数据在集合中的下标,否则打印找不到    具体找的方式:  

1. 找到数组的中间位置  

2. 检测中间位置的数据是否与要查找的数据key相等  
a: 相等,找到,打印下标,跳出循环    

b: key < arr[mid], 则key可能在arr[mid]的左半侧,继续到左半侧进行二分查找    

c: key > arr[mid], 则key可能在arr[mid]的右半侧,继续到右半侧进行二分查找          

如果找到返回下标,否则继续,直到区间中没有元素时,说明key不在集合中,打印找不到       易错点:  

1. right的右半侧区间取值,该值决定了后序的写法  

2. while循环的条件是否有等号  

3. 求中间位置的方法,直接相加除2容易造成溢出  

4. 更改left和right的边界时,不确定是否要+1和-1
方法一,采用[left, right] 区间

#include <stdio.h>
int main()
{
  int arr[] = {1,2,3,4,5,6,7,8,9,10};
  int key = 3;
  int left = 0;
  int right = sizeof(arr)/sizeof(arr[0])-1; // right位置的数据可以取到
  while(left<=right) // right位置有数据,必须要添加=号
  {
    int mid = left+(right-left)/2;
    if(arr[mid]>key) // key小于中间位置数据,说明key可能在左半侧,需要改变右边界
    {
      right = mid-1; // right位置的数据可以取到,因此right=mid-1
    }
    else if(arr[mid]<key)// key大于中间位置数据,说明key可能在右半侧,需要改变左边界
    {
      left = mid+1; // left位置的数据可以取到,因此left=mid+1
    }
    else
    {
      printf("找到了,下标是:%d\n", mid);
      break;
    }
  }
  if(left>right)
    printf("找不到\n");
  return 0;
}

方法二,采用[left, right) 区间

#include <stdio.h>
int main()
{
  int arr[] = {1,2,3,4,5,6,7,8,9,10};
  int key = 3;
  int left = 0;
  int right = sizeof(arr)/sizeof(arr[0]); // right位置的数据取不到
  while(left<right) // right位置没有数据,此处不需要添加=
  {
    int mid = left+(right-left)/2;
    if(arr[mid]>key) // key小于中间位置数据,说明key可能在左半侧,需要改变右边界
    {
      right = mid; // right位置的数据取不到,因此right=mid,不需要减1
    }
    else if(arr[mid]<key)// key大于中间位置数据,说明key可能在右半侧,需要改变左边界
    {
      left = mid+1; // left位置的数据可以取到,因此left=mid+1
    }
    else
    {
      printf("找到了,下标是:%d\n", mid);
      break;
    }
  }
  if(left>=right)
    printf("找不到\n");
  return 0;
}

二分查找的时间复杂度的问题:总共有n个元素,每次查找的区间大小就是n,n/2,n/4,…,n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数。由于n/2^k取整后>=1,即令n/2^k=1,可得k=log2n,(是以2为底,n的对数),所以时间复杂度可以表示O(logn),确实比顺序查找快不少,但是二分查找有一个较大的局限性:只能查找有序数组的元素,即组数字必须是升序或降序。


若有不足之处,希望批评指正


相关文章
|
算法 Java
折半查找算法[二分查找法]算法的实现和解决整数溢出问题~
折半查找算法[二分查找法]算法的实现和解决整数溢出问题~
|
存储 算法
【查找算法】折半查找法
【查找算法】折半查找法
|
29天前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
17 0
|
算法 C语言
C语言:使用 普通方法 和 二分查找算法(折半查找算法) 在一个有序数组中查找具体的某个数字n-2
第一步: (1). 设置初始数组:int arr[]。 (2). 生成相关变量: int n = 0; -- 存放从键盘输入的要查找的值; int i = 0; -- 循环变量;
|
6月前
|
算法
【408数据结构与算法】—折半插入排序(十六)
【408数据结构与算法】—折半插入排序(十六)
|
12月前
|
算法 C语言
C语言-折半查找(二分查找)算法详解
C语言-折半查找(二分查找)算法详解
164 0
|
搜索推荐 算法
深入浅出排序算法之直接插入排序(拓展:折半插入排序)
深入浅出排序算法之直接插入排序(拓展:折半插入排序)
|
算法 C语言
C语言:使用 普通方法 和 二分查找算法(折半查找算法) 在一个有序数组中查找具体的某个数字n-1
思路一:普通方法 (逻辑简单,在无序数组中也可以使用,但效率较低,需要逐个查找) 总体思路: