33. Search in Rotated Sorted Array

Search in Rotated Sorted Array - LeetCode

Overview

• ソートされた配列が回転している場合の探索
• 境界がどこにあるかで場合分けして、探索を行う
  • num[left] == target や nums[right] == target の場合を考慮して =を考える
  • 要素数が1の場合や、 midの計算がオーバーフローしないように注意

Go

package main

func search(nums []int, target int) int {
 left := 0
 right := len(nums) - 1

 if left == right {
  if nums[left] == target {
   return 0
  } else {
   return -1
  }
 }

 for left <= right {
  mid := left + (right-left)/2

  if nums[mid] == target {
   return mid
  }

  // border is nothing
  if nums[left] < nums[mid] && nums[mid] < nums[right] {
   if target < nums[mid] {
    right = mid
   } else {
    left = mid + 1
   }
  } else {
   // border is on the right
   if nums[left] <= nums[mid] {
    if nums[left] <= target && target < nums[mid] {
     right = mid
    } else {
     left = mid + 1
    }
   } else {
    // border is on the left
    if nums[mid] < target && target <= nums[right] {
     left = mid + 1
    } else {
     right = mid
    }
   }
  }
 }

 return -1
}