算法-二分查找算法（OC、Swift、Python）

原创

用户6004386

修改于 2019-10-18 18:04:15

8180

修改于 2019-10-18 18:04:15

文章被收录于专栏：iOS代码混淆

前言

二分查找在程序开发过程中是十分常见的算法,也是在程序员面试过程中关于算法的知识点考察过程中最常问的知识点；二分查找在实际开发过程中也常常用的到；就比如在一个一维有序数组中查找最大的一个数；我们可以每次都和数组中间的元素对比，然后缩小查找范围。

二分查找是一个非常快速高效的查找算法，因为每次查找数据查找空间都会被缩小为原理数组长度的一半，直到查找空间为空，才结束查找。

但是二分查找针对的是有序数组，而且是那种不经常变动数组；还有就是要是数据的数据量比较小，也不是适合用二分查找，毕竟遍历一次就够了,相对于去处理数据量比较大的数组时，二分查找的优势就比较明显了！

代码

这里我放上OC、Swift和Python的二分查找的代码，以便大家学习交流。

OC

- (NSInteger)halveSearch:(NSArray *)array target:(id)target{
    if(array.count == 0){
        return -1;
    }
    //标记区间的开始小标
    NSInteger start = 0;
    //标记区间结束的下标
    NSInteger end = array.count - 1;
    //标记区间中间的下标
    NSInteger middle = 0;
    
    while (start < end - 1) {
        //取区间数组里面的中间下标
        middle = start + (end - start) / 2;
        
        //中间值大于目标值
        if([array[middle] integerValue] > [target integerValue]){
            //目标值在中间值前面，将中间值赋给end作为最后一个值，在前面进行搜索取值
            end = middle;
        }else{
            //中间值小于目标值
            //将中间值赋给start作为开始值，在后面一段进行搜索
            start =  middle;
        }
        
        //如果起始值等于目标值
        if ([array[start] integerValue] == [target integerValue]) {
            return start;
        }
        
        //如果结束值等于目标值
        if ([array[end] integerValue] == [target integerValue]) {
            return end;
        }
    }
    
    return -1;
}

Swift

func halveSearch(_ array: Array<Any>, target: NSInteger) -> NSInteger {
        if array.count == 0{
            return -1
        }
        //标记区间的开始小标
        var start = 0
        //标记区间结束的下标
        var end = array.count - 1
        //标记区间中间的下标
        var middle = 0
        
        while start < end - 1 {
            //取区间数组里面的中间下标
            middle = start + (end - start) / 2
            
            //中间值大于目标值
            if (array[middle] as AnyObject).integerValue > target{
                //目标值在中间值前面，将中间值赋给end作为最后一个值，在前面进行搜索取值
                end = middle
            }else{
                //中间值小于目标值
                //将中间值赋给start作为开始值，在后面一段进行搜索
                start =  middle
            }
            
            //如果起始值等于目标值
            if (array[start] as AnyObject).integerValue == target{
                return start
            }
            
            //如果结束值等于目标值
            if (array[end] as AnyObject).integerValue == target{
                return end
            }
        }
        
        return -1
    }

Python

def halveSearch(array, target):
	if len(array) == 0:
		return -1

	# 标记区间的开始小标
	start = 0
	# 标记区间结束的下标
	end = len(array) - 1
	# 标记区间中间的下标
	middle = 0

	while start < end - 1:
		# 取区间数组里面的中间下标
		middle = int(start + (end - start) / 2)

		# 中间值大于目标值
		if array[middle] > target:
			# 目标值在中间值前面，将中间值赋给end作为最后一个值，在前面进行搜索取值
			end = middle
		else:
			# 中间值小于目标值
            # 将中间值赋给start作为开始值，在后面一段进行搜索
			start =  middle

		# 如果起始值等于目标值
		if array[start] == target:
			return start

		# 如果结束值等于目标值
		if array[end] == target:
			return end

	return -1