# 🔥 Binary search in javascript

Binary search concept seems to be easy, but it's quite difficult to apply to various problem.

• Basic binary search
• Binary search for duplicate elements
• Generalized binary search to find min/max

## ✨ I. Basic

• Both inclusive ranges `[left, right]` are used.
• Therefore `=` used in while condition in order to include for checking the same `left` and `right` case.
``````const bisect = (array, target) => {
const N = array.length;

// [left, right] : Both inclusive ranges
let left = 0;
let right = N - 1;

while (left <= right) {
const mid = Math.floor((left + right) / 2);

if (array[mid] === target) {
return mid;
} else if (array[mid] < target) {
left = mid + 1;
} else if (target < array[mid]) {
right = mid - 1;
}
}
// left is the insertion point
return left;
};
``````

## ✨ II. Binary search for duplicate elements

• The insertion point can be larger than the `length` of array.
• Half inclusive ranges `[left, right)` are used.
• `left = 0`
• `right = N`
• Search space is `[left, right)`.
• `[left, left)` is not valid region, so that `while(left < right)`.

### ✨ (II.1) left-most

• We will find `array[left] === target`
• `left` will be returned.
``````//         |
//        \/
//       target, target, target, other...
//       [left,  right)
//                          |
//                         \/
//             other..., target, other...
//                       [left, right)
// return left
``````
• If check is done in `mid`. The next space will be split into the followings.
• `[left, mid)`
• `mid`
• `[mid + 1, right)`.
``````const leftBound = (array, target, left = 0, right = array.length) => {
// [left, right)

while (left < right) {
const mid = Math.floor((left + right) / 2);

if (array[mid] === target) {
right = mid;
} else if (array[mid] < target) {
left = mid + 1;
} else if (array[mid] > target) {
right = mid;
}
}
// index
return left;

// check whether array[left] === target
// if (left === array.length) return -1
// return array[left] === target ? left : -1
};
``````

### 🔥 [object Object] : simple version

• If the mid value (`array[mid]`) is `larger or equal` to target (`array[mid] >= target`).
• we observed that `mid` is `array[mid] >= target`.
• so, we use this founding `mid` as `right`
• and then, search for the left region to find whether this is smaller `left`
• If the mid value (`array[mid]`) is `smaller` than target (`array[mid] < target`).
• we observed that `mid` is `array[mid] < target`.
• this `mid` can not be `left` because it's smaller than target.
• we need larger value `left = mid + 1`.
• next, search for the right region.
``````const leftBound = (array, target, left = 0, right = array.length) => {
// [left, right)

while (left < right) {
const mid = Math.floor((left + right) / 2);

if (array[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
// index
return left;

// check whether array[left] === target
// if (left === array.length) return -1
// return array[left] === target ? left : -1
};
``````

### 🔥 (II.2) right most point

• We will find the minimum `left` such that `array[left] > target`.
``````//                                |
//                                \/
//       target, target, target, other...
//                               [left,  right]
//                                |
//                                \/
//             other..., target, other...
//                               [left,  right]
// return (left - 1)
``````
• Final `left` is the right-most insertion point which is NOT same as `target`.
``````const rightBound = (array, target, left = 0, right = array.length) => {
// [left, right)

while (left < right) {
const mid = Math.floor((left + right) / 2);

if (array[mid] === target) {
left = mid + 1;
} else if (array[mid] < target) {
left = mid + 1;
} else if (array[mid] > target) {
right = mid;
}
}
// right-most
return left - 1;

// check whether array[left-1] === target
// if (left === 0) return -1;
// return array[left-1] === target ? left -1 : -1
};
``````

### 🔥 [object Object] : simple version

• If the mid value (`array[mid]`) is `larger` than target (`array[mid] > target`).
• we observed that `mid` is `array[mid] > target`.
• `mid` can be `right`, so that we use this founding `mid` as `right`.
• and then, search for the left region to find whether there is smaller `left`
• If the mid value (`array[mid]`) is `smaller or equal` to target (`array[mid] <= target`).
• we observed that `mid` is `array[mid] <= target`.
• we are looking for the `left` which is larger than `target`.
• this `mid` can not be `left` because it's smaller than target.
• we need larger value `left = mid + 1`.
• next, search for the right region.
• Final `left` is the right-most insertion point.
• If you need the largest maching location which is the same as the `target`, need to check whether `array[left - 1]` is `target`.
``````const rightBound = (array, target, left = 0, right = array.length) => {
// [left, right) half inclusive range
while (left < right) {
const mid = Math.floor((left + right) / 2);

// right-most
if (array[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
// right-most
return left - 1;

// check whether array[left -1] === target
// if (left === 0) return -1;
// return array[left-1] === target ? left -1 : -1
};
``````

#### 🗒️ Typical problems

• Both inclusive ranges `[left, right]` are used.
• Therefore `=` used in while condition in order to include for checking the same `left` and `right` case.

### ✨ III.0 Understand the problem and find the monotonicity

• The most difficult part.
• Understand the problem and find which variable should be changed.
• This variable must show the monotonicity feature, which makes it possible to find the minimum/maximum value by using binary search.

### 🔥 III.1 Find the minimum value

• Find the minimum value using `left` pointer.
``````const check = (num) => {
/*
------
|
----
<== true ==>
[left, right]
*/
return BOOLEAN;
};
``````
• If `mid` is in `true` region, search for smaller value `[left, mid-1]`.
• If `mid` is NOT in `true` region, search for larger value `[mid + 1, right]`.
``````// [left, right] : Both inclusive ranges

while (left <= right) {
const mid = Math.floor((left + right) / 2);

if (check(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
return left;
}
``````

### 🔥 III.2 Find the maximum value

• Find the maximum value using `right` pointer
``````const check = (num) => {
/*
-------
|
------------
<== true ==>
[left, right]
*/
return BOOLEN;
};
``````
• If `mid` is `TRUE` region, search for larger value `[mid + 1, right]`.
• If `mid` is NOT in `TRUE` region, search for smaller value `[left, mid - 1]`.
``````// [left, right] : Both inclusive ranges

while (left <= right) {
const mid = Math.floor((left + right) / 2);

if (check(mid)) {
left = mid + 1;
} else {
right = mid - 1;
}
return right;
}
``````