首页 > 代码库 > OC版二分查找
OC版二分查找
二分查找(也称折半查找)是很常见的一种在数组中查找数据的算法,作为一名程序员是应该必须会的。它的基础思想:获取数组的中间值,将数组分割成两份,利用中间值跟指定的值进行比较,如果中间值大于指定的值,就在数组的左边进行查找;如果中间值小于指定值,就在数组的右边进行查找。如此循环的执行下去,最终找到符合的值。
二分查找优点:1.速度快 2.比较次数少 3.性能好 当然了,缺点也很明显:1.必须是一个有序的数组(升序或者降序) 2.适用范围:适用不经常变动的数组
上源代码:
- (void)viewDidLoad { [super viewDidLoad]; NSArray * array1 = @[@1,@2,@3,@4,@5,@6,@7,@9]; int result = [self compare:array1 target:@9]; //在这里打印结果看是否有相等的值 NSLog(@"%d",result);}- (int)compare:(NSArray *)array target:(int)target{ if (!array.count) { return -1; } unsigned int low = 0; unsigned int high = array.count - 1; while (low <= high) { //会有一些朋友看到有些人是( low + high ) / 2这样写的,但是这样写有一点不好,就是low+high会出现整数溢出的情况,如果存在溢出,你再除以2也是没有用的,所以不能这么写 int mid = low + ((high - low)/2); //第mid项的内容 int num = [array objectAtIndex:mid]; if (target == num) { return low; }else if (num > target){ high = mid - 1;//左边进行查找 }else{ low = mid +1;//右边进行查找 } } return -1;//返回-1是没找到}
好了,简单的介绍二分查找,如果有错误,请加以指正。
OC版二分查找
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。