二分查找iOS

二分查找(也称折半查找)是很常见的一种在数组中查找数据的算法,作为一名程序员是应该必须会的。它的基础思想：获取数组的中间值，将数组分割成两份，利用查找的值跟中间值进行比较，如果查找的值大于中间值，就在数组的右边进行查找；如果查找的值小于中间值，就在数组的左边进行查找。如此循环的执行下去，最终找到符合的值。

二分查找

优点：
1.速度快 2.比较次数少 3.性能好

缺点：

1.必须是一个有序的数组（升序或者降序）
2.适用范围：适用不经常变动的数组

在没使用算法之前时间复杂度是O(N)，而在使用算法之后，时间复杂度就变成了O(logN)

NSArray * array1 = @[@3,@7,@9,@14,@25,@26,@37,@69];

NSInteger result = [self binarySearchTarget:@26 inArray:array1];//在这里打印结果看是否有相等的值

NSLog(@"%ld",(long)result);

// 在某个数组中搜索目标

- (NSInteger)binarySearchTarget:(NSInteger)target inArray:(NSArray *)arr{

if (arr.count < 1) {

//数组无元素,返回-1;

return -1;

}

// 定义三个变量第一个值下标、中间值下标、最后一个值下标

NSInteger start = 0;

NSInteger end = arr.count - 1;

NSInteger mind = 0;

// 进行循环 // 数组中第一个对象和最后一个对象之前还有其他对象则进行循环

while (start < end - 1) {

//会有一些朋友看到有些人是( start + end ) / 2这样写的,但是这样写有一点不好,就是start+end会出现整数溢出的情况,如果存在溢出,你再除以2也是没有用的,所以不能这么写

mind = start + (end - start) / 2;

// 如果中间值大于目标值

if ([arr[mind] integerValue]> target) {

end = mind; // 中间值做为最后一个值，在前半段再进行相同的搜索

}else{

start = mind;

}

// 如果第一个值和目标值相等则获取第一个值的下标

if ([arr[start] integerValue] == target) {

return start;

}

// 如果最后一个值和目标值想等则获取最后一个下标

if ([arr[end] integerValue] == target) {

return end;

}

return -1;

}

巴特西

二分查找iOS

最新文章

热门文章