翼度科技»论坛 编程开发 .net 查看内容

记录用C#写折半查找算法实现

6

主题

6

帖子

18

积分

新手上路

Rank: 1

积分
18
折半查找算法

前言

最近要考试了,重新回顾一下之前学的算法,今天是折半查找,它的平均比较次数是Log2 n
思想

给定一个有序数组A[0..n-1],和查找值K,返回K在A中的下标。
折半查找需要指定3个指针,left、right、mid,分别是左指针指向下标0,右指针指向元素末尾,mid中间值指向(left+right)/ 2向下取整。
如果A[mid] > K,中间值大于要找的K值,移动right指针,right = mid - 1
如果A[mid] < k,中间值小于要找的K值,移动left指针,left = mid + 1
如果A[mid] == K,则返回 mid
算法实现
  1. public static void Main(string[] args){
  2.     int[] A = {1,2,3,6,7,11,23,56};
  3.     int K = 23;
  4.     Console.WriteLine(Search(A,K));
  5. }
  6. public static int Search(int[] A,int K){
  7.     int left = 0;
  8.     int right = A.Length - 1;
  9.     while(left <= right){
  10.         int mid = (left + right) / 2;
  11.         if(A[mid] == K){ return mid;}
  12.         else if(A[mid]>K){
  13.             right = mid - 1;
  14.         }else{
  15.             left = mid + 1;
  16.         }
  17.     }
  18.     return -1;
  19. }
复制代码
结尾

有任何错误欢迎指正.

来源:https://www.cnblogs.com/ZYPLJ/archive/2023/03/03/17175345.html
免责声明:由于采集信息均来自互联网,如果侵犯了您的权益,请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容,谢谢合作!

上一篇: 堆排序

下一篇: .net使用DispatchProxy

举报 回复 使用道具