Binary search

Binary search 有好幾種情況，以下根據不同的情況提供相應的解法。

當然這裡有個前提，就是陣列中的元素是已經排序好的。

Binary search 有好幾中情況:

1. 找到目標值
2. 找到最後一個小於或等於目標值的元素(upper bound)
3. 找到第一個大於或等於目標值的元素(lower bound)
4. 找到第一個大於目標值的元素(upper bound + 1)
5. 找到最後一個小於目標值的元素(lower bound - 1)
6. 找到第一個等於目標值的元素(lower bound + 等於)
7. 找到最後一個等於目標值的元素(upper bound + 等於)
8. 找到第一個小於目標值的元素(沒有意義)
9. 找到最後一個大於目標值的元素(沒有意義)

扣除第一種，其他八種情況代表是三個條件的組合:

1. 包不包含目標值
2. 找到的是第一個還是最後一個
3. 找到的是大於還是小於

1. Find exact value 找到目標值

只要找到目標值，就返回它的索引。沒有找到，就返回 -1。在這個情況中，元素不會重複出現。

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

2. Find the last element that is less than or equal to the target 找到最後一個小於或等於目標值的元素(upper bound)

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] <= target) {
      result = mid
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return result
}

3. Find the first element that is greater than or equal to the target 找到第一個大於或等於目標值的元素(lower bound)

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] >= target) {
      result = mid
      right = mid - 1
    } else {
      left = mid + 1
    }
  }

  return result
}

4. Find the first element that is greater than the target 找到第一個大於目標值的元素(upper bound + 1)

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] > target) {
      result = mid
      right = mid - 1
    } else {
      left = mid + 1
    }
  }

  return result
}

5. Find the last element that is less than the target 找到最後一個小於目標值的元素(lower bound - 1)

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] < target) {
      result = mid
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return result
}

6. Find the first element that is equal to the target 找到第一個等於目標值的元素(lower bound + 等於)

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] === target) {
      result = mid
      right = mid - 1
    } else if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return result
}

7. Find the last element that is equal to the target 找到最後一個等於目標值的元素(upper bound + 等於)

function binarySearch(arr, target) {
  let left = 0
  let right = arr.length - 1
  let result = -1

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (arr[mid] === target) {
      result = mid
      left = mid + 1
    } else if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return result
}