33. 搜索旋转排序数组

33. 搜索旋转排序数组

代码

javascript

// 33. 搜索旋转排序数组：https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
// 输入：nums = [4,5,6,7,0,1,2], target = 0
// 输出：4

export function searchInRotatedSortedArray (nums, target) {
  let low = 0
  let high = nums.length - 1
  while (low <= high) {
    let mid = low + Math.floor((high - low) / 2)
    if (nums[mid] === target) {
      return mid
    }
    if (nums[low] <= nums[mid]) {
      if (nums[low] <= target && target < nums[mid]) {
        high = mid - 1
      } else {
        low = mid + 1
      }
    } else {
      if (nums[mid] < target && target <= nums[high]) {
        low = mid + 1
      } else {
        high = mid - 1
      }
    }
  }
  return -1
}

typescript

// 33. 搜索旋转排序数组：https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
// 输入：nums = [4,5,6,7,0,1,2], target = 0
// 输出：4

export function searchInRotatedSortedArray (nums: number[], target: number): number {
  let low = 0
  let high = nums.length - 1
  while (low <= high) {
    let mid = low + Math.floor((high - low) / 2)
    if (nums[mid] === target) {
      return mid
    }
    if (nums[low] <= nums[mid]) {
      if (nums[low] <= target && target < nums[mid]) {
        high = mid - 1
      } else {
        low = mid + 1
      }
    } else {
      if (nums[mid] < target && target <= nums[high]) {
        low = mid + 1
      } else {
        high = mid - 1
      }
    }
  }
  return -1
}

测试代码

test

import { expect, test } from 'vitest'
import { searchInRotatedSortedArray } from './typescript.ts'
import { searchInRotatedSortedArray as searchInRotatedSortedArrayJs } from './javascript.js'

test(`searchInRotatedSortedArray`, () => {
  expect(searchInRotatedSortedArray([4,5,6,7,0,1,2], 0)).toBe(4)
})

test(`searchInRotatedSortedArrayJs`, () => {
  expect(searchInRotatedSortedArrayJs([4,5,6,7,0,1,2], 0)).toBe(4)
})