# Rotated Array Search

[[0-Index]]

## Description

> Search for number in sorted array, with unique elements, that has been rotated by some arbitrary number. Return `-1` if it doesn't exist

**Assume array **does not contain duplicates**

---

![img](https://i.imgur.com/C2xru5r.png\Screenshot)

## Hints
- Linear Search is not an acceptable solution
- Try to solve with binary search

Note: binary search requres a **sorted** array

`const values = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`

### Non-binary Search

```javascript
const search = (val, arr) => {
  for (let i = 0; i < arr.length; i++) {
   if(val === arr[i]) {
     return i;
   }
  }
  return -1;
}
```

### Binary Search:

1. Always dealing with `lower` and `upper` limits
2. Cut at middle, if not found, split sides at middle of each side until found

```javascript
const binary = (val, arr) => {
  // create lower value
  let lower = 0;
  // create upper value
  let upper = arr.length - 1;

  // keep iterating as long as lower boundary is less than upper boundary
  while(lower <= upper) {
    // get middle index of array
    const middle = lower + Math.floor((upper - lower)/2)

    // if search val is middle # between lower and upper, return middle
    if (val === arr[middle]){
      return middle;
    }

    /* if search val is less than middle number:
        1. set upper to middle - 1
        2. set lower to middle + 1
    */
    if (val < arr[middle]){
      upper = middle - 1;
    } else {
      lower = middle + 1;
    }
  }
  return -1;
}
```

```
1. Sorted array

2. Cut in half

3. Proceed to left;
    search left

4. Proceed to right;
    search right

5. Repeat
```

## Educative Module

*Issue*: Only one half of the array remains sorted if rotated

1. If number `n` is within sorted half, it is a basic binary search
2. Otherwise, discard sorted half and keep unsorted to be examine

-- Since we're partitioning each step, `O(log n)`

Solution 1: Recursive

```javascript
let binarySearch = function(arr, start, end, key) {
  // assuming all the keys are unique.
  if (start > end) {
    return -1;
  }

  let mid = start + Math.floor((end - start) / 2);

  if (arr[mid] === key) {
    return mid;
  }

  if (arr[start] <= arr[mid] && key <= arr[mid] && key >= arr[start]) {
    return binarySearch(arr, start, mid - 1, key);
  }

  else if (arr[mid] <= arr[end] && key >= arr[mid] && key <= arr[end]) {
    return binarySearch(arr, mid + 1, end, key);
  }

  else if (arr[end] <= arr[mid]) {
    return binarySearch(arr, mid + 1, end, key);
  }

  else if (arr[start] >= arr[mid]) {
    return binarySearch(arr, start, mid - 1, key);
  }

  return -1;
};

let binarySearchRotated = function(arr, key) {
  return binarySearch(arr, 0, arr.length - 1, key);
};

let v1 = [6, 7, 1, 2, 3, 4, 5];
console.log("Key(3) found at: " + binarySearchRotated(v1, 3));
console.log("Key(6) found at: " + binarySearchRotated(v1, 6));

let v2 = [4, 5, 6, 1, 2, 3];
console.log("Key(3) found at: " + binarySearchRotated(v2, 3));
console.log("Key(6) found at: " + binarySearchRotated(v2, 6));
```

Solution 2: Iterative

### Runtime complexity
The runtime complexity of this solution is logarithmic
 `O(log n)`.

### Memory complexity
The memory complexity of this solution is constant
`O(1)`.


```javascript
let binarySearchRotated = function(arr, key) {

  start = 0;
  end = arr.length - 1;

  if (start > end){
    return -1;
  }

  while (start <= end){
    mid = start + Math.floor((end - start) / 2);

    if (arr[mid] == key){
      return mid;
    }

    if (arr[start] <= arr[mid] && key <= arr[mid] && key >= arr[start]){
      end = mid - 1;
    }

    else if (arr[mid] <= arr[end] && key >= arr[mid] && key <= arr[end]){
      start = mid + 1;
    }

    else if (arr[end] <= arr[mid]){
      start = mid + 1;
    }

    else if (arr[start] >= arr[mid]){
      end = mid - 1;
    }

    else{
      return -1;
    }
  }
  return -1;
};

let v1 = [6, 7, 1, 2, 3, 4, 5];

console.log("Key(3) found at: " + binarySearchRotated(v1, 3));
console.log("Key(6) found at: " + binarySearchRotated(v1, 6));

let v2 = [4, 5, 6, 1, 2, 3];

console.log("Key(3) found at: " + binarySearchRotated(v2, 3));
console.log("Key(6) found at: " + binarySearchRotated(v2, 6));
```
This solution works iteratively so te algo comes down to **`O(1)`** even though the logic remains the same

---

Next - [[3-SmallestCommonNumber.md]]