# Binary Search

###### tags: `LeetCode筆記`

* **Target** - the value that you are searching for
* **Index** - the current location that you are searching
* **Left, Right** - the indicies from which we use to maintain our search Space
* **Mid** - the index that we use to apply a condition to determine if we should search left or right

### Note:
* Binary Search can take many alternate forms and might **not always be as straight forward as searching for a specific value**.
* Sometimes you will have to apply **a specific condition or rule to determine which side** (left or right) to search next.

## :memo: 一、基本概念

### 組成
1. Pre-processing - Sort if collection is unsorted.
2. Binary Search - Using a loop or recursion to divide search space in half after each comparison.
3. Post-processing - Determine viable candidates in the remaining space.

### 思考
為何code寫得不一樣?
哪一個較簡單?
哪一個較佳?
*主程式最後一行結束時要回傳left還是right?

## :memo: 二、Template

### Template #1 最基本

起始條件: **left = 0, right = length - 1**
終止條件: **left > right**
向左找: **right = mid - 1**
向右找: **left = mid + 1**

int left = 0;
int right = numsSize - 1;
int mid = 0;

while (left <= right)  //是小於等於
{
    mid = (left + right) / 2;
    if (nums[mid] == target)
    {
        return mid;
    }
    else if (nums[mid] > target)
    {
        right = mid - 1;
    }
    else if (nums[mid] < target)
    {
        left = mid + 1;
    }
}
    
return -1;

**範例: Sqrt(x)**
Constraints:
0 <= x <= 2^31 - 1

int mySqrt(int x) {
    int left = 0;
    int right = x;
    long mid = 0;  //要用long
    
    while (left <= right)
    {
        mid = (left + right) / 2;
        long mid_square = mid * mid;
        if (mid_square == x)
        {
            return mid;
        }
        else if (mid_square < x)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    
    return right;  //要回傳right才對
}

**注意:** 上面這一題範例要回傳**right**才對

**數學方法:** Newton's Method (Best)

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;

        double x0 = x;
        double x1 = (x0 + x / x0) / 2.0;
        while (Math.abs(x0 - x1) >= 1) {
            x0 = x1;
            x1 = (x0 + x / x0) / 2.0;
        }

        return (int) x1;
    }
}

### Template #2 高機率在右邊?(我猜想)

起始條件: left = 0, right = length - 1
終止條件: **left == right**
向左找: right = mid
向右找: **left = mid + 1**
* Search Condition needs to access the element's immediate right neighbor
* Use the element's right neighbor to determine if the condition is met and decide whether to go left or right
* Guarantees Search Space is at least 2 in size at each step
* Post-processing required. oop/Recursion ends when you have 1 element left. Need to assess if the remaining element meets the condition.

if (numsSize == 0) {
    return -1;
}
int left = 0
int right = numsSize - 1;
while (left < right)
{
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if (nums[mid] == target)
    { 
        return mid;
    }
    else if (nums[mid] < target)
    { 
        left = mid + 1;
    }
    else
    { 
        right = mid; 
    }
}

// Post-processing:
// End Condition: left == right
if (left != numsSize() && nums[left] == target)
{
    return left;
}

return -1;

**範例: First Bad Version**


Since each version is developed based on the previous version, all the versions after a bad version are also bad.

int left = 1;
int right = n;
int mid = 0;

while (left < right)
{
    mid = left + (right - left) / 2;
    //printf("l:%d m:%d r:%d\n",left,mid,right);
    if (isBadVersion(mid) == false)
    {
        left = mid + 1;
    }
    else if (isBadVersion(mid) == true)
    {
        right = mid;
    }        
}

if (left != n && isBadVersion(left) == true)
{
    return left;
}

return right;  //不能寫-1

### Template #3 在左或在右機率一樣?(我猜想)

起始條件: left = 0, right = length - 1
終止條件: **left + 1 == right**
向左找: right = mid
向右找: **left = mid**
* Search Condition needs to access element's immediate left and right neighbors
* Use element's neighbors to determine if condition is met and decide whether to go left or right
* Gurantees Search Space is at least 3 in size at each step
* Post-processing required. Loop/Recursion ends when you have 2 elements left. Need to assess if the remaining elements meet the condition.

int left = 0;
int right = numsSize() - 1;
while (left + 1 < right)
{
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if (nums[mid] == target)
    {
        return mid;
    }
    else if (nums[mid] < target)
    {
        left = mid;
    }
    else
    {
        right = mid;
    }
}

// Post-processing:
// End Condition: left + 1 == right
if (nums[left] == target)
{
    return left;
}
if (nums[right] == target)
{
    return right;
}

return -1;

## :memo: Guess Number Higher or Lower (Easy)


### 作法
變數都要用 long long 不然不夠大

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */

class Solution {
public:
    int guessNumber(int n) {
        long long left = 1;
        long long right = n;
        long long mid = 0;
        
        while (left <= right) {
            mid = (left + right) / 2;
            
            if (guess(mid) == 0) {
                return mid;
            }
            else if (guess(mid) == 1) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        
        return right;
    }
};

## :memo: Closest Binary Search Tree Value (Easy)
Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.



### 作法 Traverse
**時間: O(N)**

class Solution {
public:
    void traverse(TreeNode* root, double target, double* diff_min, int* ans) {
        if (root == nullptr) {
            return;
        }
        
        if (root->val == target) {
            diff_min = 0;
            *ans = target;
            
            return;
        }
        
        if (abs(root->val - target) < *diff_min) {
            *diff_min = abs(root->val - target);
            *ans = root->val;
        }
        
        if (target <= root->val) {
            traverse(root->left, target, diff_min, ans);
        }
        else if (target > root->val) {
            traverse(root->right, target, diff_min, ans);
        }
        
        return;
    }
    int closestValue(TreeNode* root, double target) {
        double diff_min = INT_MAX;
        int ans = root->val;
        
        traverse(root, target, &diff_min, &ans);
        
        return ans;
    }
};

### 作法 Binary Search
**時間: O(H)**

class Solution {
public:
    int closestValue(TreeNode* root, double target) {
        int val, closest = root->val;

        while (root != nullptr) {
            val = root->val;
            closest = abs(val - target) < abs(closest - target) or (abs(val - target) == abs(closest - target) and val < closest) ? val : closest;
            root = target < val ? root->left : root->right;
        }
        
        return closest;
    }
};

## :memo: *Valid Perfect Square (Easy)

### 作法
if num == 1 要回 true

class Solution {
public:
    bool isPerfectSquare(long long num) {
        if (num == 1) {
            return true;
        }
        
        long long left = 1;
        long long right = num / 2;
        long long mid = 0;
        
        while (left <= right) {
            mid = (left + right) / 2;
            if (mid * mid == num) {
                return true;
            }
            else if (mid * mid < num) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        
        return false;
    }
};

## :memo: Find Smallest Letter Greater Than Target (Easy)

### 作法
在使用template II後要做後處理，檢查left的位置在尾端還是在中間而且letters[left]要小於等於target

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int left = 0;
        int right = letters.size() - 1;
        int mid = 0;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (letters[mid] <= target) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        
        // 要做 post-process
        if (left < letters.size() - 1 && letters[left] <= target) {
            return letters[left + 1];
        }
        else if (left == letters.size() - 1 && letters[left] <= target) {
            return letters[0];
        }
        
        return letters[left];
    }
};

## :memo: Search in Rotated Sorted Array (Medium)

### 作法
這一題要先確定mid與left的大小關係，確定從left和mid之間的大小關係，判斷後如果left小於mid代表left到mid遞增，而target介於兩者之間就向左找否則向右找，如果left大於mid代表從mid到right是遞增，而如果target介於mid與right之間就向右找否則向左找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int mid = 0;
        
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                }
                else {
                    left = mid + 1;
                }
            }
            else {
                if (target <= nums[right] && target > nums[mid]) {
                    left = mid + 1;
                }
                else {
                    right = mid - 1;
                }
            }
        }
        
        return -1;       
    }
};

## :memo: *Find Peak Element (Medium)

### 作法 my code C
這一題我寫得很冗條件太多餘，比較如下

int findPeakElement(int* nums, int numsSize){
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    
    if (numsSize == 1)
    {
        return 0;
    }
    
    if (numsSize == 2)
    {
        if (nums[0] > nums[1])
        {
            return 0;
        }
        return 1;
    }
    
    while (left < right)
    {
        mid = left + (right - left) / 2;
        //printf("l:%d m:%d r:%d\n",left,mid,right);
        if (mid - 1 >= 0 && mid + 1 <= numsSize - 1)
        {
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1])
            {
                return mid;
            }
            else if (nums[mid] > nums[mid - 1] && nums[mid] < nums[mid + 1])
            {
                left = mid + 1;
            }
            else if (nums[mid] < nums[mid - 1] && nums[mid] > nums[mid + 1])
            {
                right = mid;
            }
            else
            {
                right = mid;
            }
        }
        else
        {
            if (mid == 0 && nums[mid] > nums[mid + 1])
            {
                return mid;
            }
            else if (mid == numsSize - 1 && nums[mid] > nums[mid - 1])
            {
                return mid;
            }
        }
    }

    // if(left!=numsSize)
    // {
    //     // if((left==0 && nums[left]>nums[left+1]) || (left==numsSize-1 && nums[left]>nums[left-1]))
    //     // {
    //     //     return left;
    //     // }
    //     // else if ((nums[left]>nums[left-1] && nums[left]>nums[left+1]))
    //     // {
    //     //     return left;
    //     // }
    //     return left;
    // }
    
    return left;
}

### 作法 clean code C

int findPeakElement(int* nums, int numsSize){
    int left = 0; 
    int right = numsSize - 1;
    int mid = 0;
    
    while (left < right) 
    {
        mid = (left + right) / 2;
        if (nums[mid] > nums[mid + 1])
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    
    return left;
}

## :memo: *Find K Closest Elements (Medium)
Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array.
The result should also be sorted in ascending order.


### 作法 Binary Search To Find The Left Bound
一開始right=size-k，然後比較x與mid的距離和x與mid+k的距離誰大，x與mid+k的距離較大代表mid+k以後都不會是答案，所以向左找，反之亦然，這一題數線數學很重要





int left = 0;
int right = arrSize - k;
int mid = 0;

int* ret = (int*) malloc(sizeof(int) * k);
*returnSize = k;

while (left < right)
{
    mid = (left + right) / 2;
    if (x - arr[mid] > arr[mid + k] - x)   //good job!
    {
        left = mid + 1;
    }
    else
    {
        right = mid;
    }
}

for (int i = 0; i < k; i++)
{
    ret[i] = arr[left + i];
}

return ret;

## :memo: Search in a Sorted Array of Unknown Size (Medium)
You have a sorted array of unique elements and an unknown size.


### 作法
**時間: O(logT) where T is an index of target value.**

/**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* class ArrayReader {
*   public:
*     int get(int index);
* };
*/
 
class Solution {
public:
    int search(const ArrayReader& reader, int target) {
        if (reader.get(0) == target) {
            return 0;
        }
        
        // search boundaries 一直乘以2直到超過target
        int left = 0;
        int right = 1;
        while (reader.get(right) < target) {
            left = right;
            right <<= 1 ;
        }
        
        //  binary search
        int pivot;
        int num;
        while (left <= right) {
            pivot = left +((right - left) >> 1);
            num = reader.get(pivot);
            
            if (num == target) {
                return pivot;
            }
            if (num > target) {
                right = pivot - 1;
            }
            else {
                left = pivot + 1;
            }
        }
        
        // there is no target element
        return -1;
    }
};

## :memo: *Pow(x, n) (Medium)
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).


### 作法 fast power algorithm
**時間: O(logN)**
**空間: O(1)**

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double ans = 1;
        double current_product = x;
        for (long long i = N; i; i /= 2) {
            if (i % 2 == 1) {
                ans = ans * current_product;
            }
            current_product = current_product * current_product;
        }
        
        return ans;
    }
};

## :memo: *Find the Duplicate Number (Medium)

### 作法 Cycle Detection
這一題solution有很多作法，此作法比Binary Search快，比Hash Table省空間
**時間: O(N)**
**空間: O(1)**



int tortoise = nums[0];
int hare = nums[0];

do
{
    tortoise = nums[tortoise];
    hare = nums[nums[hare]];
}while (tortoise != hare);

tortoise = nums[0];

while (tortoise != hare)
{
    tortoise = nums[tortoise];
    hare = nums[hare];
}

return hare;

## :memo: Find Minimum in Rotated Sorted Array (Medium)

### 作法 my code C
我的作法是先讓size==1,2的獨立處理後判斷mid-1和mid+1有沒有超出範圍，再用mid跟mid-1和mid+1比較然後再跟right比判斷遞增或驟降決定向左找或向右找，比較如下
my code:

int findMin(int* nums, int numsSize){
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    
    if (numsSize == 1)
    {
        return nums[0];
    }
    
    if (numsSize == 2)
    {
        if (nums[0] < nums[1])
        {
            return nums[0];
        }
        return nums[1];
    }
    
    while (left < right)
    {
        mid = left + (right - left) / 2;
        //printf("l:%d m:%d r:%d\n",left,mid,right);
        if (mid - 1 >= 0 && mid + 1 <= numsSize - 1)
        {   
            if (nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1])
            {
                return nums[mid];
            }
            else if (nums[mid] < nums[right])
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        else
        {
            // if(mid==0 && nums[mid]<nums[mid+1])
            // {
            //     return nums[mid];
            // }
            // else if(mid==numsSize-1 && nums[mid]<nums[mid-1])
            // {
            //     return nums[mid];
            // }
            return nums[mid];
        }
    }
    
    return nums[left];
}

### 作法 solution

int findMin(int* nums, int numsSize){
    if (numsSize == 1) 
    {
        return nums[0];
    }

    // initializing left and right pointers.
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;

    // if the last element is greater than the first element then there is no
    // rotation.
    // e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.
    // Hence the smallest element is first element. A[0]
    if (nums[right] > nums[0])
    {
        return nums[0];
    }

    // Binary search way
    while (right >= left)
    {
        // Find the mid element
        mid = left + (right - left) / 2;

        // if the mid element is greater than its next element then mid+1 element is the
        // smallest
        // This point would be the point of change. From higher to lower value.
        if (nums[mid] > nums[mid + 1])
        {
            return nums[mid + 1];
        }

        // if the mid element is lesser than its previous element then mid element is
        // the smallest
        if (nums[mid - 1] > nums[mid])
        {
            return nums[mid];
        }

        // if the mid elements value is greater than the 0th element this means
        // the least value is still somewhere to the right as we are still dealing with
        // elements
        // greater than nums[0]
        if (nums[mid] > nums[0])
        {
            left = mid + 1;
        }
        else
        {
            // if nums[0] is greater than the mid value then this means the smallest value
            // is somewhere to
            // the left
            right = mid - 1;
        }
    }
    
    return INT_MAX;
}

## :memo: Find Minimum in Rotated Sorted Array II (Hard)
這一題數字會重複

### 作法

// template #2
int findMin(int* nums, int numsSize){
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    
    while (left < right)
    {
        mid = left + (right - left) / 2;
        //printf("l:%d m:%d r:%d\n",left,mid,right);
        if (nums[mid] < nums[right])
        {
            right = mid;
        }
        else if (nums[mid] > nums[right])
        {
            left = mid + 1;
        }
        else
        {
            right--;   //key point!!
        }       
    }
    
    return nums[left];
}

## :memo: Median of Two Sorted Arrays (Hard)

### 作法
i和j分別從兩個sorted陣列左邊開始讀，像是MergeSort的做法一樣排序，很標準的寫並記錄數值

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int n = nums1Size + nums2Size;
    float nums3[n];
    float median;
    int i,j,k,mid;
    i = j = k = 0;

    while (i < nums1Size && j < nums2Size)
    {
        if (nums1[i] < nums2[j])
        {
            nums3[k++] = nums1[i++];
        }
        else
        {
            nums3[k++] = nums2[j++];
        }
    }
    for (; i < nums1Size; i++)
    {
        nums3[k++] = nums1[i];
    }
    for (; j < nums2Size; j++)
    {
        nums3[k++] = nums2[j];
    }

    if (n % 2 == 0)
    {
        mid = n / 2;
        median = (nums3[mid] + nums3[mid - 1]) / 2;

        return median;
    }
    else
    {
        median = nums3[n / 2];
        return median;
    }

    return;
}

## :memo: Find K-th Smallest Pair Distance (Hard)

### 作法
We will use a sliding window approach to count the number of pairs with distance <= guess.
For every possible right, we maintain the loop invariant: left is the smallest value such that nums[right] - nums[left] <= guess.
Then, the number of pairs with right as it's right-most endpoint is right - left, and we add all of these up.

int cmp(const void *a, const void *b)
{
    return *(const int *) a - *(const int *) b;
}

int smallestDistancePair(int* nums, int numsSize, int k){
    qsort(nums, numsSize, sizeof(int), cmp);
    
    int lo = 0;
    int hi = nums[numsSize - 1] - nums[0];   //key point
    int mi = 0;
    
    while (lo < hi)
    {
        mi = (lo + hi) / 2;
        int count = 0;
        int left = 0;
        for(int right = 0; right < numsSize; ++right)
        {
            while (nums[right] - nums[left] > mi)
            {
                left++;
            }
            count += (right - left);
        }
        //count = number of pairs with distance <= mi
        if (count >= k)
        {
            hi = mi;
        }
        else
        {
            lo = mi + 1;
        }
    }
    
    return lo;
}

## :memo: Split Array Largest Sum (Hard)

### 作法
minimumSubarraysRequired

int minimumSubarraysRequired(int* nums, int numsSize, int maxSumAllowed){
    int currentSum = 0;
    int splitsRequired = 0;
    
    for (int i = 0; i < numsSize; i++)
    {
        // Add element only if the sum doesn't exceed maxSumAllowed
        if (currentSum+nums[i] <= maxSumAllowed)
        {
            currentSum += nums[i];
        }
        else
        {
            // If the element addition makes sum more than maxSumAllowed
            // Increment the splits required and reset sum
            currentSum = nums[i];
            splitsRequired++;
        }
    }
    
    // Return the number of subarrays, which is the number of splits + 1
    return splitsRequired + 1;
}

int splitArray(int* nums, int numsSize, int m){
    // Find the sum of all elements and the maximum element
    int sum = 0;
    int maxElement = INT_MIN;
    
    for (int i = 0; i < numsSize; i++)
    {
        sum += nums[i];
        maxElement = fmax(maxElement, nums[i]);
    }
    
    // Define the left and right boundary of binary search
    int left = maxElement;
    int right = sum;
    int minimumLargestSplitSum = 0;
    while (left <= right)
    {
        // Find the mid value
        int maxSumAllowed = left + (right - left) / 2;
        
        // Find the minimum splits. If splitsRequired is less than
        // or equal to m move towards left i.e., smaller values
        if (minimumSubarraysRequired(nums, numsSize, maxSumAllowed) <= m)
        {
            right = maxSumAllowed - 1;
            minimumLargestSplitSum = maxSumAllowed;
        }
        else
        {
            // Move towards right if splitsRequired is more than m
            left = maxSumAllowed + 1;
        }
    }
    
    return minimumLargestSplitSum;
}

## :memo: Tips
有些題目會隱藏著Binary Search解法，需要思考二分的可能性

條件不會只是單純比mid與target的大小，會變成以mid為基礎做變化的條件式，要去思考如何寫

二元搜尋法方法簡單運用卻靈活，要聰明的談條件，確定100%正確的case當作第一個if，其餘cases都塞到1個else，不用過多的else if包裝，這樣反而導致錯誤

畫圖去trace，case by case

## :memo: 刷題檢討
很多題目寫得太冗，或是想不到數學意義的表示式，最後不知道回傳left還是right，要了解切一半後左右半邊代表的意義，以及有時要逆向思考，看似>其實要向左找，看似<其實要向右找，最重要的是那一個二分的條件(第一個if)要100%正確，
if(){}
else if(){}
else{}
的順序也會影響演算法正確性，有可能順序不對就錯了
如:找誰的倍數(3,5,15)
15要先

**想要提高演算法的速率，直覺可以想到二元搜尋!!**