# Posts tagged as “binary search”

Write an efficient algorithm that searches for a value in an `m x n` matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

```Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
```

Example 2:

```Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
```

Constraints:

• `m == matrix.length`
• `n == matrix[i].length`
• `1 <= m, n <= 100`
• `-104 <= matrix[i][j], target <= 104`

Solution 1: (DFS)

``````/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
return dfs(matrix, target, 0, 0);
};

function dfs(matrix, target, x, y) {
let rows = matrix.length;
let cols = matrix[0].length;

// exit recursion condition, reach to the end;
if (y === rows) return false;

// traverse from left to right, then next row
let nextX = (x + 1) % cols;
let nextY = nextX === 0 ? y + 1 : y;

if (matrix[y][x] === target)
return true;
else
return dfs(matrix, target, nextX, nextY);

return false;
}``````

Solution 2: (Binary Search) Better and Faster!

• Time complexity: O(log(mn))
• Space complexity: O(1)
``````var searchMatrix = function(matrix, target) {
let cols = matrix[0].length;
// 	treat 2D as 1D, use binary search
let l = 0;
let r = matrix.length * cols;
while (l < r) {
let mid = l + Math.floor((r - l) / 2);
let row = Math.floor(mid / cols);
let col = mid % cols;
if (matrix[row][col] === target) {
return true;
} else if (matrix[row][col] > target) {
r = mid;
} else {
l = mid + 1;
}
}
return false;
};``````

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.

Example 1:

```Input: nums = [1,3,5,6], target = 5
Output: 2
```

Example 2:

```Input: nums = [1,3,5,6], target = 2
Output: 1
```

Example 3:

```Input: nums = [1,3,5,6], target = 7
Output: 4
```

Example 4:

```Input: nums = [1,3,5,6], target = 0
Output: 0
```

Example 5:

```Input: nums = [1], target = 0
Output: 0
```

Constraints:

• `1 <= nums.length <= 104`
• `-104 <= nums[i] <= 104`
• `nums` contains distinct values sorted in ascending order.
• `-104 <= target <= 104`

Idea:

Use Binary Search

• Time complexity: O(logn)
• Space complexity: O(1)

Solution:

``````/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
let l = 0;
let r = nums.length;

while (l < r) {
let mid = l + Math.floor((r - l) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] > target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};``````

Given an array of integers `nums` sorted in ascending order, find the starting and ending position of a given `target` value.

If `target` is not found in the array, return `[-1, -1]`.

Follow up: Could you write an algorithm with `O(log n)` runtime complexity?

Example 1:

```Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
```

Example 2:

```Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
```

Example 3:

```Input: nums = [], target = 0
Output: [-1,-1]
```

Constraints:

• `0 <= nums.length <= 105`
• `-109 <= nums[i] <= 109`
• `nums` is a non-decreasing array.
• `-109 <= target <= 109`

Idea:

Binary Search

Solution:

``````/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
let leftBound = -1;
let rightBound = -1;
let l = 0;
let r = nums.length - 1;

while (l <= r) {
let mid = l + Math.floor((r - l) / 2);
if (nums[mid] === target) {
leftBound = mid;
r = mid - 1;
} else if (nums[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}

l = 0;
r = nums.length - 1;
while (l <= r) {
let mid = l + Math.floor((r - l) / 2);
if (nums[mid] === target) {
rightBound = mid;
l = mid + 1;
} else if (nums[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return [leftBound, rightBound];
};``````

There is an integer array `nums` sorted in ascending order (with distinct values).

Prior to 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,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 rotation and an integer `target`, return the index of `target` if it is in `nums`, or `-1` if it is not in `nums`.

Example 1:

```Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
```

Example 2:

```Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
```

Example 3:

```Input: nums = [1], target = 0
Output: -1
```

Constraints:

• `1 <= nums.length <= 5000`
• `-104 <= nums[i] <= 104`
• All values of `nums` are unique.
• `nums` is guaranteed to be rotated at some pivot.
• `-104 <= target <= 104`

Idea:

Binary Search: the idea is to create a recursive function that takes l and h as range in input and the key.

```1) Find middle point mid = (l + h)/2
2) If key is present at middle point, return mid.
3) Else If nums[l..mid] is sorted
a) If key to be searched lies in range from nums[l]
to nums[mid], recur for nums[l..mid].
b) Else recur for nums[mid+1..h]
4) Else (nums[mid+1..h] must be sorted)
a) If key to be searched lies in range from nums[mid+1]
to nums[h], recur for nums[mid+1..h].
b) Else recur for nums[l..mid] ```

Solution:

``````/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
return searching(nums, 0, nums.length - 1, target);
};

function searching(nums, l, h, target) {
if (l > h) return -1;

let mid = Math.floor((l + h) / 2);
// basic case: found
if (target === nums[mid]) return mid;

// if nums[l...mid] is sorted
if (nums[l] <= nums[mid]) { /// make sure is <=
if (target >= nums[l] && target <= nums[mid])
return searching(nums, l, mid - 1, target);
else
return searching(nums, mid + 1, h, target)
}

// if nums[l...mid] is notesorted, then nums[mid+1..h] must be sorted
if (target >= nums[mid] && target <= nums[h])
return searching(nums, mid + 1, h, target);
else
return searching(nums, l, mid - 1, target);
}``````