美文网首页程序员@IT·互联网
二分查找(oc/java/python/scala)

二分查找(oc/java/python/scala)

作者: 狼牙战士 | 来源:发表于2017-05-24 18:41 被阅读0次

    原创

    查找过程演示:

    在数组[130,150,170,190,210,230,250,270,290,310]中查找数字190,红色为二分线(折半线),灰色为查找区域,黑色为排除区域。

    SYJ二分查找演示.gif

    二分查找优缺点:

    二分查找(折半查找)优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。时间复杂度可以表示O(h)=O(log2n),以2为底,n的对数。比如数组长度为10,最多找4次。

    objectIve-c实现代码:

    #import <Foundation/Foundation.h>
    
    int search(NSArray *array,int item){
        int x = 1;
        int low = 0;
        int high = (int)[array count] - 1;
        while (low <= high) {
            NSLog(@"第%d次比较",x);
            x++;
            int mid = (high+low)/2;
            if(item == [array[mid] intValue]){
                NSLog(@"%d找到了,在第%d个位置",item,mid);
                return mid;
            }else if(item < [array[mid] intValue]){
                NSLog(@"%d比%d大,继续查找",[array[mid] intValue],item);
                high = mid-1;
            }else{
                NSLog(@"%d比%d小,继续查找",[array[mid] intValue],item);
                low = mid+1;
            }
        }
        return -1;
    }
    
    int main(int argc, const char * argv[]) {
        @autoreleasepool {
            NSLog(@"请输入要查询的数字:");
            int x;
            scanf("%d",&x);
            NSArray *array = @[@1,@3,@5,@7,@9,@11,@13,@15,@17,@19,@21,@23,@25];
            int jieguo = search(array,x);
            if(jieguo == -1){
                NSLog(@"没找到要查找的数字");
            }
        }
        return 0;
    }
    

    运行截图:

    1.png

    java实现代码:

    import java.util.Scanner;
    public class PaiXu{
        public static void main(String[] args){
            Integer[] haha = {1,3,5,7,9,11,13,15,17,19,21,23,25,27};
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入您要查找的值:");
            int z = sc.nextInt();
            int y = binarySearch(haha,z);
            if(y == -1){
                System.out.println("要查找的值不存在");
            }
        }
    
        public static int binarySearch(Integer[] srcArray,int des){
            int x = 1;
            int low = 0;
            int high = srcArray.length-1;
            while(low<=high){
                System.out.println("第"+x+"次比较");
                x++;
                int mid = (high+low)/2;
                if(des == srcArray[mid]){
                    System.out.println(des+"找到了,在第"+mid+"个位置");
                    return mid;
                }else if(des < srcArray[mid]){
                    System.out.println(srcArray[mid]+"比"+des+"大,继续查找");
                    high = mid-1;
                }else{
                    System.out.println(srcArray[mid]+"比"+des+"小,继续查找");
                    low = mid+1;
                }
            }
            return -1;
        }
    }
    

    运行截图:

    2.png

    Python实现代码:

    def binary_search(list,item):
        x = 1
        low = 0
        high = len(list)-1
        while low <= high:
            print('第%d次比较'%x)
            x=x+1
            mid = (low+high)//2
            guess = list[mid]
            if guess == item:
                print('找到了,在第%d个位置'%mid)
                return mid
            if guess > item:
                print('%d比%d大,继续查找'%(guess,item))
                high = mid-1
            else:
                print('%d比%d小,继续查找'%(guess,item))
                low = mid+1
        print('找不到%d'%item)
        return None
    my_list = [1,3,5,7,9,11,13,15,17,19,21,23,25]
    z = int(input('请输入要查找的数字:'))
    binary_search(my_list,z)
    

    运行截图:

    scala实现代码:

    object ErFen{
        def main(args:Array[String]){
            //var z:Array[Int] = new Array[Int](14);
            //var z = new Array[Int](14);
            var z = Array(1,3,5,7,9,11,13,15,17,19,21,23,25,27);
            var y:Int = search(z,15);
            if(y == -1){
                println("要查找的值不存在");
            }
        }
    
        def search(arr:Array[Int],des:Int):Int={
            var x:Int = 1;
            var low:Int = 0;
            var high:Int = arr.length-1;
            while(low <= high){
                println("第"+x+"次比较");
                x += 1;
                var mid:Int = (high+low)/2;
                if(des == arr(mid)){
                    println(des+"找到了,在第"+mid+"个位置");
                    return mid;
                }else if(des < arr(mid)){
                    println(arr(mid)+"比"+des+"大,继续查找");
                    high = mid - 1;
                }else{
                    println(arr(mid)+"比"+des+"小,继续查找");
                    low = mid + 1;
                }
            }
            return -1;
        }
    }
    

    运行截图:

    Snip20170602_4.png

    相关文章

      网友评论

        本文标题:二分查找(oc/java/python/scala)

        本文链接:https://www.haomeiwen.com/subject/cfamzttx.html