## Binary Search in Rotated Sorted Array

Binary search is one of the most elementary algorithms in computer science. To find an element in a sorted array or linked list binary search is always preferred as it takes half the time of the linear search. ie O(Log N). This article covers recursive and iterative methods in binary search and finding an element in the rotated sorted array.

## Binary search | 0 | heading |

Binary search can be solved in a recursive fashion using the divide and rule method or iterative method using two pointer method. | 1 | paragraph |

## Recursive binary search template | 2 | subheading |

- Like any other divide and rule algorithm, we first recursively divide an array into two and search the element in either halves.
- Before we start the algorithm we cover the base case if the array is empty. If we got an empty array we should return False i.e element is not in the array.
- First, we get the midpoint of the array by dividing the length by 2. If the element at mid index is equal to target we return True.
- If the element at mid index is greater than the target then we know we have to find it in the first half so we call the same function with the first half of the array.
- If the element at mid index is less than the target then we know we have to find it in the second half so we call the same function with the second half of the array.
- While recursively search if we run out of elements to search we are going to hit the base case and we return False.
| 3 | list |

```
def bsearch(arr, target):
#arr is the array we want to search in
#base condition if arr is empty
if len(arr) == 0:
return False
mid = len(arr) // 2
if arr[mid] == target:
#we found the element return the index
return True
elif target < arr[mid]:
#recursively search in first half of array arr
return bsearch(arr[:mid], target)
else:
#recursively search in second half of array arr
return bsearch(arr[mid+1:], target)
arr = [3,6,12,45,67]
bsearch(arr, 67) #True
``` | 4 | code |

The problem with the above algorithm is when we want to find the index of the element. Since on every recursive call, we are changing our array size we lose the original length of the array. Therefore we can't find the exact midpoint as our midpoint. We can use the iterative method for finding the index. | 5 | paragraph |

## Iterative binary search template | 6 | subheading |

Promoted Promoted - Here we use two pointers left and right. Left is assigned to the first element of the array and right is assigned to right the last element.
- We use a while loop to find the index of the target. On every iteration, we calculate the midpoint by addition of left and right pointer and then dividing by 2.
- If the arr[mid] is equal to the target then we return mid.
- If arr[mid] is greater than target then we need to search in the first half so we assign mid-1 to right.
- If arr[mid] is less than target then we need to search in the second half so we assign mid+1 to left.
| 7 | list |

```
def bsearch(arr, target):
#assign left to first element
left=0
#assign left to last element
right=len(arr)-1
#run the while loop untill right > left
while left<=right:
#calculate new mid
mid = (left+right)//2
if arr[mid]==target:
#we found the target at mid
return mid
elif arr[mid]>target:
#search in first half by assigning
#mid to right
right=mid-1
else:
#search in second half by assigning
#mid to left
left=mid+1
return -1
arr = [3,6,12,45,67]
bsearch(arr, 67) #4
``` | 8 | code |

## Binary search library in Python | 9 | subheading |

Python has a library called bisect which can directly be used to find the index in log N time. | 10 | paragraph |

## Search Insert Position | 11 | subheading |

Search Insert Position | 12 | link |

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity. | 13 | paragraph |

Promoted Promoted ```
Input: nums = [1,3,5,6], target = 5
Output: 2
``` | 14 | code |

```
from bisect import bisect_left
def searchInsert(nums, target):
return bisect_left(nums, target)
``` | 15 | code |

## Square Root of Integer | 16 | subheading |

- We can use binary search for finding the square root of the integer. It uses exactly the same algorithm as the iterative method.
- Here we are trying to find a mid such that mid square is equal to x.
- If the number is lower than mid square we change right to mid-1
- If the number is greater than the mid square we change left to mid+1
| 17 | list |

```
def sqrt(x):
#assign 0 to left
left = 0
#assign x to right
right = x
#run a loop
while left <= right:
#calculate mid based on new left and right
mid = (left + right)//2
#check if x lies between mid^2 and (mid+1)^2
if mid * mid <= x < (mid+1)*(mid+1):
return mid
#if x is less than mid^2, assign right to mid-1 to check for lower numbers
elif x < mid * mid:
right = mid - 1
#if x is greater than mid^2, assign left to mid+1 to check for higher numbers
else:
left = mid + 1
sqrt(144) #return 12
``` | 18 | code |

## Search in Rotated Sorted Array | 19 | subheading |

Search in Rotated Sorted Array | 20 | link |

Promoted Promoted 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. | 21 | paragraph |

- To first find the solution we need to understand how the array is rotated. If the array is [1 2 3 4 5 6 7], the array is not rotated and we get mid at 4(index 3). If the array is [3 4 5 6 7 1 2], the array is left rotated and the mid is 6. If the array is [6 7 1 2 3 4 5], it is right rotated with mid as 2.
- To determine if the array is left or right rotated we need to see both corners of the array. For a non-rotated array, we should get arr[left] < arr[mid] < arr[right]. If it is left rotated arr[mid]>arr[right] and if it is right rotated arr[mid]<arr[left]
- Since now we found if it is left or right rotated we can use the binary search with handling the above case.
- So the first step is we find if the halves are ordered, then if the target lies in that half, we perform the same operation as we do in regular binary search, else we are going to do an opposite binary search.
| 22 | list |

```
def search(nums, target):
left = 0
right = len(nums)-1
while left <= right:
mid = (left + right)//2
if nums[mid] == target:
return mid
# the first half is ordered
if nums[left] <= nums[mid]:
# if target is in the first half
if nums[left] <= target < nums[mid]:
#do regular binary search as
#elem between L and M are not rotated
right = mid - 1
else:
#search in opposite direction (left rotated so serach in second half)
left = mid + 1
# the second half is ordered
else:
# if target is in the second half
if nums[mid] < target <= nums[right]:
#do regular binary search
#elem between L and M are not rotated
left = mid + 1
else:
#search in opposite (right rotated so serach in first half)
right = mid - 1
return -1
``` | 22 | code |

## Search in Rotated Sorted Array II (duplicate values) | 23 | subheading |

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values). Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= 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,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4]. Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums. You must decrease the overall operation steps as much as possible. | 24 | paragraph |

Search in Rotated Sorted Array II | 25 | link |

- To handle duplication we need only to check one more condition if arr[left] and arr[mid] are the same. If they are we need to increment left by 1.
- We can use a while loop until arr[left] and arr[right] are not equal.
| 26 | list |

```
def search(nums, target):
left = 0
right = len(nums)-1
while left <= right:
mid = (left + right)//2
if nums[mid] == target:
return mid
#condtion to check duplicate
while left < mid and nums[left] == nums[mid]:
left += 1
# the first half is ordered
if nums[left] <= nums[mid]:
# if target is in the first half
if nums[left] <= target < nums[mid]:
#do regular binary search as
#elem between L and M are not rotated
right = mid - 1
else:
#search in opposite as direction (left rotated)
left = mid + 1
# the second half is ordered
else:
# if target is in the second half
if nums[mid] < target <= nums[right]:
#do regular binary search
#elem between L and M are not rotated
left = mid + 1
else:
#search in opposite (right rotated)
right = mid - 1
return -1
``` | 27 | code |