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

在我的主頁和github上可以看到更多的關于leetcode的解題報告！（因為不知道為什么掘金沒有將其發布出來，目前已經聯系掘金客服）

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

author: thomas

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是數組8
復制代碼

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

思路

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

• 方法一：

  • 我們的思路是對原數組使用兩次二分查找法，分別找出一個起始和結束位置
• 方法二：利用二分法找到起始位置，然后向右遍歷，找到邊界

代碼

• 方法一

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; // 得到結束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的情況),再判斷剩下的,最后得到的結果就是要找的多個目標值target的最左邊的值
• 2、如果我們先判斷arr[mid] > target(也就是先判斷大于target的情況),再判斷剩下的,最后得到的結果就是要找的多個目標值target的最右邊的值

No35：Search Insert Position(Easy)

題目

從給定排好順序的數組，找出給定目標數字下標，存在則返回下標，不存在則返回目標數應該插入的位置下標。 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
復制代碼

思路

思路就是每次取中間，如果等于目標即返回，否則根據大小關系切去一半。因此算法復雜度是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
復制代碼

注意:二分法有一個好處:就是當循環結束時:

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

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