Brooke

一、題目

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

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

 

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1

 

Constraints:

• 1 <= nums.length <= 104
• -104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

 

二、程式作法

/*寫法一*/
public class Solution
{
    public int Search(int[] nums, int target)
    {
        int left = 0;
        int right = nums.Length - 1;
        int pivot = (nums.Length - 1) / 2;

        while (left <= right)
        {
            if (target < nums[pivot])
            {
                right = pivot - 1;
                pivot = left + (right - left) / 2;
            }
            else if (target > nums[pivot])
            {
                left = pivot + 1;
                pivot = left + (right - left) / 2;
            }
            else
                return pivot;
        }

        return -1;
    }
}

/*寫法二*/
/*
public class Solution
{
    public int Search(int[] nums, int target)
    {
        int upBound = nums.Length - 1;
        int lowBound = 0;
        while (lowBound <= upBound)
        {
            int pivot = lowBound + (upBound - lowBound) / 2;

            if (target == nums[pivot]) return pivot;

            if (target > nums[pivot])
                lowBound = pivot + 1;
            else
                upBound = pivot - 1;
        }
        return -1;
    }
}
*/

 

三、思路筆記

1、最直覺的解法為從第零個找到最後一個，但時間複雜度是 O(n)。

2、第二種解法是，已知陣列為已排序，所以可以一開始從中間找，

如果比目的小，則從左邊的中間剖一對半來找；

如果比目的大，則從右邊的中間剖一對半來找，依這流程找到為止。

 

四、相關主題

Binary Search