leetcode 搜索旋转排序数组 golang

lucasgao · · 83 次点击 · · 开始浏览    

81. 搜索旋转排序数组 II

解题思路

二分的变形,我们之前二分查找基于这样的一个假设:我们定位到一个元素后,这个元素的前后分别都是单调的。
但是这边的数组是旋转的。
所以我们需要修改的是判定逻辑

  1. 如果我们可以判定出来 那边是旋转的,那边是自增的。则可以通过边界判断
  2. 如果不行,则进行递归。

代码实现

func search(nums []int, target int) bool {
    i,j := 0,len(nums)-1
    A := nums
    for i<=j{
        mid := (i+j)/2
        if A[mid]==target{
            return true
        }
        if (A[mid]==A[j]||A[mid]==A[i]) && (search(nums[mid+1:j+1],target) || search(nums[i:mid],target)){
            return true
        }
      
        if A[mid] < A[j]{
            if target > A[mid] && target <= A[j]{
                i = mid+1
            }else{
                j = mid-1
            }
        }else{
            if target >= A[i] && target < A[mid]{
                j = mid-1
            }else{
                i = mid+1
            }
        }
    }
    return false
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:lucasgao

查看原文:leetcode 搜索旋转排序数组 golang

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

83 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传