原文題目

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

題目摘要

1. 若target位於Input陣列中，則回傳其索引值。
2. 若target不在Input陣列中，則將其插入適當位置（按升序排列）並回傳其索引值。

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

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

解題思路

1. 設定左右指標：
   • 首先，設定left和right指標分別為陣列第一位和最後一位。
2. 找到中間點：
   • 我們在給定的陣列中找出中間點的元素 mid。
3. 二分搜尋：
   • 如果 nums[mid] 等於 target，則直接返回 mid 作為目標值的索引。
   • 如果 nums[mid] 小於 target，則將 left 指標移動到 mid + 1。
   • 如果 nums[mid] 大於 target，則將 right 指標移動到 mid - 1。
4. 確定插入位置：
   • 如果二分搜尋結束後仍然沒有找到目標值，left 指標會指向目標值應該插入的位置。

程式碼

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0; //設立左指標為陣列第一位，索引值為0
        int right = nums.length - 1; //設立右指標為陣列最後一位，索引值為陣列長-1
        while (left <= right) {
            int mid = (left + right) / 2; //設定中間值
            //如果target在nums中
            if (nums[mid] > target) { //當中間值大於目標值則目標值位於中間值左側
                right = mid - 1;//將範圍限制在左指標與中間值前一位（新右指標）
            }
            else if (nums[mid] < target){ //當中間值小於目標值則目標值位於中間值右側
                left = mid + 1;//將範圍限制在中間值後一位（新左指標）與右指標
            } 
            else { //當中間值即為目標值則回傳中間值索引
                return mid; 
            }
        }
        //如果target不在nums中，最終的左指標即為插入位置的索引值
        return left;        
    }
}

結論

這題可以想像成你在餐廳點餐時，想要找到一個空桌。假設餐廳裡的桌子是按照人數多少來排序的，比如2人桌、4人桌、6人桌等等。你帶著3個朋友進來，想要找到剛好適合的桌子。如果沒有找到4人桌，你會選擇下一個合適的，比如6人桌。在這個過程中，你不會從第一張桌子開始一張張找，而是直接看中間的桌子，然後決定要往前還是往後找，直到找到最合適的桌子。這樣的方式就像二分搜尋法，可以快速確定你應該坐在哪張桌子上，也不會耽誤太多時間。這就是二分搜尋法在生活上的應用，快速而有效。