一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 245|回复: 0
收起左侧

[二分/排序/搜索] Kotlin 中一种二分查找的技巧

[复制链接] |只看干货 |刷题, 二分/排序/搜索
我的人缘0

升级   70.5%


分享帖子到朋友圈
kamm | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (49)
 
 
2% (1)    👎

注册一亩三分地论坛,查看更多干货!

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

x

/*
新手上路,请慷慨加分
Kotlin 中一种二分查找的技巧

一种在排序的数组中寻找最后一个valid的element的pattern
注意和面试官确认是不是可以用任意库函数

为什么:二分查找很容易写错,用这种方法可以不用自己写二分查找,工作中也可以用到,最大程度的利用库函数

*/


fun validate(e: Int) : Boolean {
    /* 这里只是简单判断,实际应用场景中可能这一步需要比较复杂的计算*/
    return e < 9
}

// list is sorted
fun findLastValid(list:List<Int>) :Int?{
    val insertion = list.binarySearch {
        // 注意比target小的应该return -1 大的return 1
        if(validate(it)) -1 else 1
    }
    return if(-insertion -1 >0) list[-insertion - 2] else null
}

println(findLastValid(listOf(3,7,11)))
println(findLastValid(listOf(23,25, 27)))
println(findLastValid(listOf(0,1,2,3)))
println(findLastValid(listOf()))

// 应用举例:LC 278(这个有点cheat)LC 410

/* 如果面试官非要你实现二分查找一下是kotlin自己的实现
新手上路,请慷慨加分
public fun <T> List<T>.binarySearch(fromIndex: Int = 0, toIndex: Int = size, comparison: (T) -> Int): Int {
    rangeCheck(size, fromIndex, toIndex)

    var low = fromIndex
    var high = toIndex - 1

    while (low <= high) {
        val mid = (low + high).ushr(1) // safe from overflows
        val midVal = get(mid)
        val cmp = comparison(midVal)

        if (cmp < 0)
            low = mid + 1
        else if (cmp > 0)
            high = mid - 1
        else
            return mid // key found
    }
    return -(low + 1)  // key not found
}
*/

评分

参与人数 1大米 +3 收起 理由
14417335 + 3

查看全部评分


上一篇:现在想面试成功Google level 5 或者其它著名公司的 senior SWE 需要哪些技能
下一篇:请教大家一个LRU实现的问题
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

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