Binary Search

正常用法

• 需要sorted
• 一般不带duplicate,有duplicate就有变化

log(n)

• k numbers ---> k/2 numbers

Basic Model

int end = nums.length - 1;
int start = 0;

while (end > start+1) {
    int mid = start + (end - start) / 2;
    if (nums[mid] == target) {
        end = mid;
    } else if (nums[mid] > target) {
        end = mid;
    } else {
        start = mid;
    }
}

if (nums[end] == target) {
    return end;
} else if(nums[start] == target) {
    return start;
}