Algorithm - binary search algorithm (OC, Swift, Python)

Preface

Binary search is a very common algorithm in the process of program development, and it is also the most frequently asked knowledge point in the process of exploring the algorithm knowledge point in the process of programmer interview; binary search is also often used in the actual development process; for example, we can find the largest number in a one-dimensional ordered array; we can compare with the elements in the middle of the array every time, and then reduce the search Find scope.

Binary search is a very fast and efficient search algorithm, because every time the search space of the search data will be reduced to half of the length of the principle array, and the search will not end until the search space is empty.

But binary search is for an ordered array, and it's the kind of array that doesn't change frequently; and if the data volume is small, it's not suitable to use binary search, after all, it's enough to traverse once. Compared with dealing with arrays with large data volume, the advantage of binary search is obvious!

Code

Here I put the binary search code of OC, Swift and Python for you to learn and communicate.

OC

- (NSInteger)halveSearch:(NSArray *)array target:(id)target{
    if(array.count == 0){
        return -1;
    }
    //Start of marker interval
    NSInteger start = 0;
    //Subscript marking end of interval
    NSInteger end = array.count - 1;
    //Subscript in the middle of marked interval
    NSInteger middle = 0;
    
    while (start < end - 1) {
        //Take the middle subscript in the interval array
        middle = start + (end - start) / 2;
        
        //Middle value is greater than target value
        if([array[middle] integerValue] > [target integerValue]){
            //The target value is in front of the middle value. Assign the middle value to end as the last value, and search for the value in front.
            end = middle;
        }else{
            //Middle value is less than target value
            //Assign the middle value to start as the start value, and search in the next section
            start =  middle;
        }
        
        //If the starting value is equal to the target value
        if ([array[start] integerValue] == [target integerValue]) {
            return start;
        }
        
        //If the end value is equal to the target value
        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
        }
        //Start of marker interval
        var start = 0
        //Subscript marking end of interval
        var end = array.count - 1
        //Subscript in the middle of marked interval
        var middle = 0
        
        while start < end - 1 {
            //Take the middle subscript in the interval array
            middle = start + (end - start) / 2
            
            //Middle value is greater than target value
            if (array[middle] as AnyObject).integerValue > target{
                //The target value is in front of the middle value. Assign the middle value to end as the last value, and search for the value in front.
                end = middle
            }else{
                //Middle value is less than target value
                //Assign the middle value to start as the start value, and search in the next section
                start =  middle
            }
            
            //If the starting value is equal to the target value
            if (array[start] as AnyObject).integerValue == target{
                return start
            }
            
            //If the end value is equal to the target value
            if (array[end] as AnyObject).integerValue == target{
                return end
            }
        }
        
        return -1
    }

Python

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

    # Start of marker interval
    start = 0
    # Subscript marking end of interval
    end = len(array) - 1
    # Subscript in the middle of marked interval
    middle = 0

    while start < end - 1:
        # Take the middle subscript in the interval array
        middle = int(start + (end - start) / 2)

        # Middle value is greater than target value
        if array[middle] > target:
            # The target value is in front of the middle value. Assign the middle value to end as the last value, and search for the value in front.
            end = middle
        else:
            # Middle value is less than target value
            # Assign the middle value to start as the start value, and search in the next section
            start =  middle

        # If the starting value is equal to the target value
        if array[start] == target:
            return start

        # If the end value is equal to the target value
        if array[end] == target:
            return end

    return -1

Concluding remarks

You are welcome to put forward valuable opinions and suggestions, and also welcome to exchange 365152048!

CSDN blog https://zfj1128.blog.csdn.net
GITEE home page https://gitee.com/zfj1128
GITHUB home page https://github.com/zfjsyqk

Tags: Python less Swift github

Posted on Fri, 18 Oct 2019 18:12:37 -0700 by madmax