Promoted
Promoted

Binary Search in Rotated Sorted Array

Topic: Algorithms

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

0heading

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

1paragraph

Recursive binary search template

2subheading
  • 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.
3list
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
4code

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.

5paragraph

Iterative binary search template

6subheading
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.
7list
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
8code

Binary search library in Python

9subheading

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

10paragraph

Search Insert Position

11subheading

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.

13paragraph
Promoted
Promoted
Input: nums = [1,3,5,6], target = 5 Output: 2
14code
from bisect import bisect_left def searchInsert(nums, target): return bisect_left(nums, target)
15code

Square Root of Integer

16subheading
  • 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
17list
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
18code

Search in Rotated Sorted Array

19subheading
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.

21paragraph
  • 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.
22list
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
22code

Search in Rotated Sorted Array II (duplicate values)

23subheading

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.

24paragraph
  • 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.
26list
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
27code