找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

微信名称:美国米群网

微 信 号:MeetQun

微信QQ:群: 320065698

查看: 305|回复: 3
收起左侧

[基础刷题题目讨论] 对于Sorted Array采用binary Search的两种解法(小练手)

[复制链接]

8

主题

2

精华

57

积分

米群网会员

Rank: 2

积分
57
发表于 11-26-2016 03:08 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
题目:Given a sorted array of integers, return the index of the given key. Return -1 if not found.
此题一看就知道采用divide and conquer
解法一: Time O(logn)  Space O(logn)
  int binarySearch(int[] a, int key){
     return binarySearchRec(a,key,0,a.length-1);
  }
  int  binarySearchRec(int[] a,int key,int low ,int high){
    if(low>high){
       return -1;
  }
  int mid=low+(high-low)/2;
   if(a[mid]==key){
     return mid;
   }else if(key<a[mid]){
    return binarySearchRec(a,key,low,mid-1);
}else{
    return binarySearchRec(a,key,mid+1,high);
}
}
解法二:Time O(logn)  Space O(1)
int binarySearchIterative(int[] a, int key){
           int low=0;
           int high=a.length-1;
           while(low<=high){
                   int mid=low+(high-low)/2;
                   if(a[mid]==key){
                           return mid;
                   }else if(a[mid]>key){
                           high=mid-1;
                   }else{
                           low=mid+1;
                   }
           }
           return -1;
   }

have fun

0

主题

0

精华

0

积分

新米人

Rank: 1

积分
0
发表于 11-26-2016 03:08 AM | 显示全部楼层
感谢kathytree85分享~~~
回复 支持 反对

使用道具 举报

0

主题

0

精华

11

积分

新米人

Rank: 1

积分
11
发表于 11-28-2016 12:01 PM 来自美国米群网手机版 | 显示全部楼层
感谢kathytree85分享~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表