LeetCode 75 Level 1 - Day 7 Binary Search

704. Binary Search

• 題目連結
• 難易度：Easy

題目敘述

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.

預設函數

int search(int* nums, int numsSize, int target){

}

題目限制

• 
• 
• All the integers in nums are unique.
• nums is sorted in ascending order.

解題過程及程式碼

本題是基本的二分搜尋，給一個陣列存放著數值並由小到大排列著，再給一個數值要回傳該數值若在陣列中的位置，若該數值不在陣列中則回傳-1，解題想法就是不停確認資料最中間的元素。

• 確認中間元素是不是我們要找的目標值?
• 若中間元素大於目標值，目標值在較小的半部，下一個檢查的範圍就可以縮小一半。
• 若中間元素小於目標值，目標值在較大的半部，下一個檢查的範圍就可以縮小一半。
• 重複以上過程直到剩下的半部數量為1，剩下的若是目標值就找到了，若剩下的不是目標值就表示找不到。

程式碼上傳

int search(int* nums, int numsSize, int target){
    int next_index, next_size, index_start;

    next_index = 0;
    next_size = numsSize;
    index_start = 0;

    if ((next_size == 1) && (nums[0] == target)) {
        return 0;
    }

    next_index = next_size / 2;

    while (next_size > 1) {
        next_index = index_start + (next_size / 2);

        if (nums[next_index] < target) {  // 中間元素 < 目標值

            if (next_size % 2) {
                next_size = (next_size - 1) / 2;
            } else {
                next_size = (next_size / 2) - 1;
            }

            index_start = next_index + 1;
            if ((next_size == 1) && (nums[next_index + 1] == target)) {
                return next_index + 1;
            }

        } else if (nums[next_index] > target) {  // 中間元素 > 目標值

            if (next_size % 2) {
                next_size = (next_size - 1) / 2;
            } else {
                next_size = (next_size / 2);
            }

            if ((next_size == 1) && (nums[next_index - 1] == target)) {
                return next_index - 1;
            }

        } else {
            return next_index;
        }
    }
    return -1;
}

參考資料

• 二分搜尋演算法 - 維基百科

今天就到這邊，謝謝大家!