Binary Search的變型
===
[TOC]

BS使用在sorted nums，常用於連續的數字中找特定的數字
可以在暴力解O(N)的情況下變成O(logN)

## 基本型

這個條件下nums每個數值是唯一的
值得注意的點:
* right要不要包含最後一個元素，還是等於size
我喜歡包含
* while條件l要不要包含r，也就是<還是<=
我喜歡<=
* 每次條件判斷時候mid這個數值要不要留著，還是直接捨棄
我喜歡左右都捨棄
* 計算mid有很多種方法，
* (l+r)/2 容易overflow
* l + (r-l)/2 相較於上一個沒這麼容易overflow

#include <stdio.h>
#define size 6
int BS(int nums[], int target)
{
    int l= 0, r= size-1;
    while(l<= r)
    {
        int mid= l+ (r-l)/2;
        if(nums[mid] == target) return mid;
        if(nums[mid]< target) l= mid+1;
        else r= mid-1;
    }
    return -1;
}

int main()
{
    int nums[]= {1,3,5,7,9,10};
    
    int input;
    
    while(1)
    {
        scanf("%d", &input);
        printf("input %d is located in %d\n", input, BS(nums, input));
    }
   

    return 0;
}

## nums中的每個元素不唯一，返回最左邊的target

換句話說，我們去找==第一個小於target的數，在把index+1==就是我們要的

這邊假設要找的target存在nums，如果要處理不存在的話，就再看一下找出來的答案是不是要找的target

nums[mid]是不是等於target不重要了，我們要找target的左邊那個數，所以我們盡量靠左，讓相等時去推r，最後就r就是第一個小於target的數，r+1就是最左邊的target

#include <stdio.h>
#define size 13
int BS(int nums[], int target)
{
    int l= 0, r= size-1;
    while(l<= r)
    {
        int mid= l+ (r-l)/2;
        if(nums[mid]< target) l= mid+1;
        else r= mid-1;
    }
    return r+1;
}

int main()
{
    int nums[]= {1,3,3,3,3,3,4,4,5,5,5,10,10};
    
    int input;
    
    while(1)
    {
        scanf("%d", &input);
        printf("input %d is located in %d\n", input, BS(nums, input));
    }
   

    return 0;
}

## nums中的每個元素不唯一，返回最右邊的target

換句話說，找到第一個大於target的數再把index-1，==另外的用途是找一個陣列中是否存在大於target的數==

跟第二個相反，我們想往右邊靠，所以nums[mid]==target時，我們去推l，最後l應該會落在最右邊的target，r會落在最右邊的target-1，所以r+1就是我們要的

如果是要判斷是否存在大於target的數，就去判斷r最後是不是超出size

#include <stdio.h>
#define size 13
int BS(int nums[], int target)
{
    int l= 0, r= size-1;
    while(l<= r)
    {
        int mid= l+ (r-l)/2;
        if(nums[mid]<= target) l= mid+1;
        else r= mid-1;
    }
    return r+1;
}

int main()
{
    int nums[]= {1,3,3,3,3,3,4,4,5,5,5,10,10};
    
    int input;
    
    while(1)
    {
        scanf("%d", &input);
        printf("the first greater than input %d number is %d\n", input, nums[BS(nums, input)]);
    }
  
    return 0;
}