# Search in rotated sorted array

There is an integer array nums sorted in ascending order (with **distinct** values).

Prior to being passed to your function, nums is **possibly rotated** at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (**0-indexed**). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums **after** the possible rotation and an integer target, return *the index of *target* if it is in *nums*, or *-1* if it is not in *nums.

You must write an algorithm with O(log n) runtime complexity.

```
var search = function(nums, target) {
let start = 0, end = nums.length - 1;
let mid = Math.floor((start + end) / 2);
while (start <= end) {
mid = Math.floor((start + end) / 2);
if (target === nums[mid]) {
return mid;
}
if (nums[start] <= nums[mid]) {
if (nums[start] <= target && nums[mid] >= target) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
if (nums[end] >= target && nums[mid] <= target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
```

There are many ways to solve this problem but they all use some variation of binary search or binary search applied many times. I think this may be a popular problem for interviews because it throws a wrench in the cookie cutter binary search template that many people memorize.

## Related Problems

A **transformation sequence** from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter.

Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.

sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return *all the ***shortest transformation sequences*** from* beginWord *to* endWord*, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words *[beginWord, s1, s2, ..., sk].

Given an array of **distinct** integers candidates and a target integer target, return *a list of all ***unique combinations*** of *candidates* where the chosen numbers sum to *target*.* You may return the combinations in **any order**.

The **same** number may be chosen from candidates an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you **must** take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Given an array nums of n integers where nums[i] is in the range [1, n], return *an array of all the integers in the range* [1, n] *that do not appear in* nums.