附上我的github倉庫，會不斷更新leetcode解題答案，提供一個思路，大家共勉

希望可以給star，鼓勵繼續(xù)更新解題思路

author: thomas

image

No34：Search for Range(Medium)

題目

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example

Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4]. // 下標3，4是數(shù)組8

這道題讓我們在一個有序整數(shù)數(shù)組中尋找相同目標值的起始和結(jié)束位置,沒如果沒有找到就返回[-1,-1]

思路

這道題讓我們在一個有序整數(shù)數(shù)組中尋找相同目標值的起始和結(jié)束位置，而且限定了時間復雜度為O(logn)，這是典型的二分查找法的時間復雜度，所以這道題我們也需要用此方法。

• 方法一：
  - 我們的思路是對原數(shù)組使用兩次二分查找法，分別找出一個起始和結(jié)束位置

• 方法二：利用二分法找到起始位置，然后向右遍歷，找到邊界

代碼

• 方法一

let arr1 = [1,1,2,2,3,4,4,7,8];
let arr = [5,7,7,8,8,10],
  target = 8;
let searchRange = function(arr, target) {
  let len = arr.length,
    res = [-1, -1];
  for (let i = 0, j = len-1; i <= j;) {
    let mid = Math.floor((i + j) / 2);
    if (arr[mid] < target) { // 先判斷小于target的情況
      i = mid + 1;
    }else {
      j = mid - 1; // 應對剛好i = mid + 1后就指向了target值
      if (arr[mid] === target) {
        res[0] = mid; // 得到起始index
      }
    }
  }

  for (let i = 0, j = len-1; i <= j;) {
    let mid = Math.floor((i + j) / 2);
    if (arr[mid] > target) {// 先判斷大于target的情況
      j = mid - 1;
    }else {
      i = mid + 1; // 應對剛好i = mid + 1后就指向了target值
      if (arr[mid] === target) {
        res[1] = mid; // 得到結(jié)束index
      }
    }
  }

  return res;
};
console.log(searchRange(arr,target)); // [3, 4]

• 方法二

/**
 * 方法2
 *
 * 找到res[0]之后，就向右遍歷，直到不是該值，就可以得到右邊界了
 * 時間復雜度沒上面的方法好
 */

let searchRange1 = function(arr, target) {
  let len = arr.length,
    res = [-1, -1];
  for (let i = 0, j = len-1; i <= j;) {
    let mid = Math.floor((i + j) / 2);
    if (arr[mid] < target) {
      i = mid + 1;
    }else {
      j = mid - 1; // 應對剛好i = mid + 1后就指向了target值
      if (arr[mid] === target) {
        res[0] = mid; // 得到最左邊的值
      }
    }
  }
  let k;
  res[1] = res[0];
  for (k = res[0] + 1; k < len; k++) { // 找到右邊界
    if (arr[k] === target) {
      res[1] += 1;
    }
  }

  return res;
};
console.log(searchRange1([1],1)); // [0, 0]
console.log(searchRange1([2,2],2)); // [0, 1]
console.log(searchRange1([5,7,7,8,8,10],8)); // [3, 4]
console.log(searchRange1([1,3],1)); // [0, 0]
console.log(searchRange1([3,3,3],3)); // [0, 0]

注：二分法：其假設我們找到目標值（但是有多個目標值連在一起）

• 1、如果我們先判斷arr[mid] < target(先判斷小于target的情況),再判斷剩下的,最后得到的結(jié)果就是要找的多個目標值target的最左邊的值
• 2、如果我們先判斷arr[mid] > target(也就是先判斷大于target的情況),再判斷剩下的,最后得到的結(jié)果就是要找的多個目標值target的最右邊的值

No35：Search Insert Position(Easy)

題目

從給定排好順序的數(shù)組，找出給定目標數(shù)字下標，存在則返回下標，不存在則返回目標數(shù)應該插入的位置下標。
Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 4:

Input: [1,3,5,6], 0
Output: 0

思路

思路就是每次取中間，如果等于目標即返回，否則根據(jù)大小關系切去一半。因此算法復雜度是O(logn)，空間復雜度O(1)

代碼

let arr = [1,3,5,6],
    target = 5;

let searchInset = function(arr, target) {
  let len = arr.length,
            res = 0;
  for (let i = 0, j = len -1; i <= j;) {
    let mid = Math.floor((i+j)/2);
  if (arr[mid] === target) {
            return mid;
  }
  if (arr[mid] < target) {
      i = mid + 1;
      res = mid+1; // 更新res
        }else {
        j = mid - 1;
        }
    }
    return res; //
}
console.log(searchInset(arr,target)); // 2
console.log(searchInset([1,3,5,6],2)); // 2

注意:二分法有一個好處:就是當循環(huán)結(jié)束時:

(1)如果找到目標元素，那么就返回當前位置

(2)如果沒有找到目標元素，那么i一定停在恰好比目標大的index上，j一定停在恰好比目標小的index上，所以個人比較推薦這種實現(xiàn)方式。(初始i在左，j在右)