Modified Binary Search
function search(nums: number[], target: number): number {
// O(n) X
// return nums.indexOf(target);
let left = 0,
right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
const isLeftSideSorted = nums[left] <= nums[mid];
if (isLeftSideSorted) {
// CASE1 : left half is sorted
// if (target >= nums[left] && target < nums[mid]) {
const isTargetInLeft = target >= nums[left] && target < nums[mid];
if (isTargetInLeft) {
right = mid - 1; // Move left
} else {
left = mid + 1; // Move right
}
} else {
// CASE2 : Right half is sorted
// if (target > nums[mid] && target <= nums[right]) {
const isTargetInRight = target > nums[mid] && target <= nums[right];
if (isTargetInRight) {
left = mid + 1; // Move right
} else {
right = mid - 1; // Move left
}
}
}
return -1;
}
Recursive
function search(nums: number[],
target: number,
start: number = 0,
end: number = nums.length - 1
): number {
const mid = start + Math.floor((end - start) / 2);
if (nums[mid] === target) {
return mid;
}
if (end <= start) return -1;
// Left half is sorted
if (nums[start] <= nums[mid]) {
if (nums[start] <= target && target < nums[mid]) {
return search(nums, target, start, mid - 1);
} else {
return search(nums, target, mid + 1, end);
}
} else {
if (nums[mid] < target && target <= nums[end]) {
return search(nums, target, mid + 1, end);
} else {
return search(nums, target, start, mid - 1);
}
}
}
function findMin(nums: number[]): number {
let left = 0, right = nums.length -1 ;
let minIndex = nums.length - 1;
while (left <= right){
const mid = left + Math.floor((right - left) / 2);
if(nums[mid] <= nums[nums.length - 1]){
minIndex = mid;
right = mid -1 ;
} else{
left= mid + 1;
}
}
return nums[minIndex];
};
both axes sorted in a ascending order : O(m + n)
// both axes sorted in a ascending order
function searchMatrixSimple(matrix: number[][], target: number): boolean {
let r = 0,
c = matrix[0].length - 1;
while (r < matrix.length && c >= 0) {
if (matrix[r][c] === target) return true;
if (target > matrix[r][c]) {
r++;
} else {
c--;
}
}
return false;
}
O(M * logn) : for loop + binary search
// finding rowIndex and colIndex
function searchMatrix(matrix: number[][], target: number): number[] {
const m = matrix.length;
const n = matrix[0].length;
for (let col = 0; col < n; col++) {
const rowIndex = binarySearch(matrix[col], target);
if (rowIndex !== -1) return [rowIndex, col];
}
return [-1, -1];
}
function binarySearch(rowArr: number[], target: number): number {
let left = 0,
right = rowArr.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (rowArr[mid] === target) return mid;
if (rowArr[left] <= target && target < rowArr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}