How to use Modified Binary Search with Pivot Detection In Javascript
In this approach, we first find the pivot index of the rotated array. The pivot index is the index where the rotation occurs. Once we have the pivot index, we can perform a modified binary search considering the pivot to determine the target element.
- Find the pivot index:
- We initialize two pointers,
left
andright
, pointing to the start and end of the array, respectively. - While
left
is less thanright
, we find the middle element. - If the middle element is greater than the element at the right pointer, it indicates that the pivot lies to the right of the middle element. So, we set
left = mid + 1
. - Otherwise, the pivot lies to the left of the middle element or at the middle element itself. In this case, we set
right = mid
. - After the loop,
left
will be pointing to the pivot index.
- We initialize two pointers,
- Perform modified binary search:
- Based on the value of the target element and the first element of the array, we determine whether to search in the left half or the right half of the array.
- We perform a binary search considering the pivot index to find the target element.
Example:
const searchInRotatedArray = (nums, target) => {
let left = 0;
let right = nums.length - 1;
// Find the pivot index
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
const pivot = left;
// Perform modified binary search
left = 0;
right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const rotatedMid = (mid + pivot) % nums.length;
if (nums[rotatedMid] === target) {
return rotatedMid;
} else if (nums[rotatedMid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
};
const rotatedArray = [5, 6, 7, 8, 9, 10, 1, 2, 3];
const target = 3;
console.log(searchInRotatedArray(rotatedArray, target));
Output
8
JavaScript Program to Search a Target Value in a Rotated Array
In this article, we are going to implement a JavaScript program to Search for a target value in a rotated array.
Table of Content
- Using Binary Search
- Using Linear Search
- Using Recursive Function
- Using Modified Binary Search with Pivot Detection