iT邦幫忙

0

【LeetCode with C: A Series of Problem-Solving Techniques】-- Binary Search

  • 分享至 

  • xImage
  •  

Description

704. Binary Search
Easy
Topics
Companies
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 <= 10^4
-10^4 < nums[i], target < 10^4
All the integers in nums are unique.
nums is sorted in ascending order.

Answer and Explaining

int search(int* nums, int numsSize, int target) {
    int left = 0;  // 初始化左pointer,指向陣列的起始位置
    int right = numsSize - 1;  // 初始化右pointer,指向陣列的結束位置

    // 當左pointer小於或等於右pointer時,繼續迴圈
    while (left <= right) {
        // 計算中間索引,使用 (right - left) / 2 
        int mid = left + (right - left) / 2;

        // 如果中間值等於目標值,則返回中間索引
        if (nums[mid] == target) {
            return mid;
        // 如果中間值小於目標值,則將左pointer移到中間索引的右邊
        } else if (nums[mid] < target) {
            left = mid + 1;
        // 如果中間值大於目標值,則將右pointer移到中間索引的左邊
        } else {
            right = mid - 1;
        }
    }

    return -1;  
}

Testing

int search(int* nums, int numsSize, int target) {
    int left = 0;  // 初始化左pointer,指向陣列的起始位置
    int right = numsSize - 1;  // 初始化右pointer,指向陣列的結束位置

    // 當左pointer小於或等於右pointer時,繼續迴圈
    while (left <= right) {
        // 計算中間索引,使用 (right - left) / 2 
        int mid = left + (right - left) / 2;

        // 如果中間值等於目標值,則返回中間索引
        if (nums[mid] == target) {
            return mid;
        // 如果中間值小於目標值,則將左pointer移到中間索引的右邊
        } else if (nums[mid] < target) {
            left = mid + 1;
        // 如果中間值大於目標值,則將右pointer移到中間索引的左邊
        } else {
            right = mid - 1;
        }
    }

    return -1;  
}

#include <stdio.h>

int main() {
    int nums[] = {-1, 0, 3, 5, 9, 12};  // 範例有序整數陣列
    int target = 9;  // 目標值
    int numsSize = sizeof(nums) / sizeof(nums[0]);  // 計算陣列的大小

    // 呼叫二分搜尋函數並輸出結果
    int result = search(nums, numsSize, target);
    printf("目標值 %d 的索引為: %d\n", target, result);  // 預期輸出: 目標值 9 的索引為: 4

    return 0;
}

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言