【面试必刷TOP101】二分查找-I & 二维数组中的查找

简介: 【面试必刷TOP101】二分查找-I & 二维数组中的查找

题目:二分查找-I_牛客题霸_牛客网 (nowcoder.com)

题目的接口:

package main
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param target int整型 
 * @return int整型
*/
func search( nums []int ,  target int ) int {
    // write code here
}

解题思路:

这是最基本的二分查找算法,就是在一个普通的升序数组中写二分,非常的简单,直接进行二分查找就行了,下面是我的二分模板:

       while (left <= right) {

           int mid = left + (right - left) / 2;

           if ( ... ) left = mid + 1;

           else if ( ... ) right = mid - 1;

           else if ( ... ) return mid;

       }

(这个是我当年写 C++ 的时候总结的二分模板,其实算法都是相通的)

代码:

package main
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param target int整型 
 * @return int整型
*/
func search( nums []int ,  target int ) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] > target {
            right = mid - 1
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            return mid
        }
    }
    return -1
}

过啦!!!

题目:二维数组中的查找_牛客题霸_牛客网 (nowcoder.com)

题目的接口:

package main
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param target int整型 
 * @param array int整型二维数组 
 * @return bool布尔型
*/
func Find( target int ,  array [][]int ) bool {
    // write code here
}

解题思路:

这道题很经典,但是并不是算是一道标准的二分查找的题目(不知道牛客为什么要放进二分专题里面),用二分查找理论上也是可以的,但是没有必要,使用的二分查找的复杂度依然是 O(N),所以没必要,

这道经典的题目有一个很经典的解法,我比较习惯就是从右上角开始查找,如果大了就往左,如果小了就往下(这道题其实是剑指 Offer 里面的经典题目)

代码:

package main
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param target int整型 
 * @param array int整型二维数组 
 * @return bool布尔型
*/
func Find( target int ,  array [][]int ) bool {
    i, j := len(array)-1, 0
    for i >= 0 && j < len(array[0]) {
        if array[i][j] > target {
            i--
        } else if array[i][j] < target {
            j++
        } else {
            return true
        }
    }
    return false
}

过啦!!!

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

相关文章
|
7月前
【面试必刷TOP101】寻找峰值 & 数组中的逆序对
【面试必刷TOP101】寻找峰值 & 数组中的逆序对
29 0
|
7月前
【面试必刷TOP101】删除链表的倒数第n个节点 & 两个链表的第一个公共结点
【面试必刷TOP101】删除链表的倒数第n个节点 & 两个链表的第一个公共结点
28 0
|
13天前
(力扣)面试题04. 二维数组中的查找
(力扣)面试题04. 二维数组中的查找
23 0
|
6天前
|
C++
【一刷《剑指Offer》】面试题 3:二维数组中的查找
【一刷《剑指Offer》】面试题 3:二维数组中的查找
|
13天前
|
机器学习/深度学习 算法 搜索推荐
|
13天前
LeetCode(面试题:二维数组中的查找)
LeetCode(面试题:二维数组中的查找)
23 0
|
7月前
|
算法 Go C++
【面试必刷TOP101】 删除有序链表中重复的元素-I & 删除有序链表中重复的元素-II
【面试必刷TOP101】 删除有序链表中重复的元素-I & 删除有序链表中重复的元素-II
31 0
|
7月前
【面试必刷TOP101】判断一个链表是否为回文结构 & 链表的奇偶重排
【面试必刷TOP101】判断一个链表是否为回文结构 & 链表的奇偶重排
22 0
|
7月前
|
算法
【面试必刷TOP101】链表相加 & 单链表的排序
【面试必刷TOP101】链表相加 & 单链表的排序
23 0
|
7月前
【面试必刷TOP101】链表中环的入口结点 & 链表中倒数最后k个结点
【面试必刷TOP101】链表中环的入口结点 & 链表中倒数最后k个结点
17 0