{"id":34822,"date":"2024-11-01T09:32:24","date_gmt":"2024-11-01T09:32:24","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34822"},"modified":"2024-11-01T11:26:23","modified_gmt":"2024-11-01T11:26:23","slug":"swift-coding-test-course-binary-search","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34822\/","title":{"rendered":"Swift Coding Test Course, Binary Search"},"content":{"rendered":"

<\/p>\n

1. Overview of Binary Search<\/h2>\n

\n Binary Search is an algorithm used to find the position of a specific value in a sorted array.
\n It is very efficient as it divides the array in half to find the desired value,
\n having a time complexity of O(log n) in both average and worst cases.
\n This is significantly better than the O(n) of linear search.\n<\/p>\n

1.1 Principle of Binary Search<\/h3>\n

\n Binary Search proceeds with the following steps:\n<\/p>\n

    \n
  1. Check if the array to be searched is sorted.<\/li>\n
  2. Set the start index and end index.<\/li>\n
  3. Calculate the middle index.<\/li>\n
  4. Compare the middle value to the value you want to find.<\/li>\n
  5. If the value to be found is less than the middle value, set the end index to middle index – 1,
    \n and if it’s greater, set the start index to middle index + 1.<\/li>\n
  6. Repeat until the value is found or the start index is greater than the end index.<\/li>\n<\/ol>\n

    2. Algorithm Problems<\/h2>\n

    \n Now, let’s look at a problem that utilizes binary search.\n<\/p>\n

    Problem: Finding the Index of a Specific Number in an Array<\/h3>\n
    \nGiven an integer array nums<\/code> and an integer target<\/code>, \nwrite a function that returns the index of target<\/code> if it exists in the array nums<\/code>, \nor -1 if it does not exist.\n\nExample:\nInput: nums = [-1,0,3,5,9,12], target = 9\nOutput: 4\n\nInput: nums = [-1,0,3,5,9,12], target = 2\nOutput: -1\n<\/pre>\n
    3. Problem Solving Process<\/h3>\n
    \n    To solve the problem, we will use the binary search algorithm to find the target<\/code> value in the array.
    \n    I will explain step by step.\n<\/p>\n
    3.1 Function Definition<\/h4>\n
    \n    First, we define the binarySearch<\/code> function that will perform the binary search.
    \n    This function takes the array nums<\/code> and the target<\/code> value as arguments.\n<\/p>\n
    \n\nfunc binarySearch(nums: [Int], target: Int) -> Int {\n    var left = 0\n    var right = nums.count - 1\n\n    while left <= right {\n        let mid = left + (right - left) \/ 2\n\n        if nums[mid] == target {\n            return mid\n        } else if nums[mid] < target {\n            left = mid + 1\n        } else {\n            right = mid - 1\n        }\n    }\n    return -1\n}\n<\/code>\n<\/pre>\n
    3.2 Variable Initialization<\/h4>\n
    \n    Initialize the variables left<\/code> and right<\/code> to 0 and the length of the array - 1, respectively.
    \n    left<\/code> represents the starting index of the search range, and right<\/code> represents the ending index.\n<\/p>\n
    3.3 Calculating the Middle Value<\/h4>\n
    \nUse the while<\/code> loop to repeat until left<\/code> is less than or equal to right<\/code>.
    \n    In each iteration, calculate the middle index mid<\/code>.
    \n    When calculating the middle value, use left + (right - left) \/ 2<\/code> to prevent overflow.\n<\/p>\n
    3.4 Comparing the Target<\/h4>\n
    \n    If the middle value nums[mid]<\/code> equals target<\/code>, return that index mid<\/code>.
    \n    If nums[mid]<\/code> is less than target<\/code>,
    \n    set left<\/code> to mid + 1<\/code> to search the right half.
    \n    Conversely, if nums[mid]<\/code> is greater than target<\/code>,
    \n    set right<\/code> to mid - 1<\/code> to search the left half.\n<\/p>\n
    3.5 Returning the Result<\/h4>\n
    \n    When the loop ends, it means target<\/code> does not exist in the array, so return -1.\n<\/p>\n
    4. Full Code<\/h3>\n
    \n\nfunc binarySearch(nums: [Int], target: Int) -> Int {\n    var left = 0\n    var right = nums.count - 1\n\n    while left <= right {\n        let mid = left + (right - left) \/ 2\n\n        if nums[mid] == target {\n            return mid\n        } else if nums[mid] < target {\n            left = mid + 1\n        } else {\n            right = mid - 1\n        }\n    }\n    return -1\n}\n\n\/\/ Example usage\nlet nums = [-1, 0, 3, 5, 9, 12]\nlet target = 9\nlet result = binarySearch(nums: nums, target: target)\nprint(result) \/\/ 4\n<\/code>\n<\/pre>\n
    5. Advantages and Disadvantages of Binary Search<\/h2>\n
    5.1 Advantages<\/h3>\n
    \n    The main advantage of binary search is its fast search speed.
    \n    It shows significantly higher performance compared to linear search when dealing with very large datasets.\n<\/p>\n
    5.2 Disadvantages<\/h3>\n
    \n    However, a disadvantage of using binary search is that the data must be sorted.
    \n    Frequent insertion and deletion of data may require separate sorting operations.\n<\/p>\n
    6. Conclusion<\/h2>\n
    \n    Binary search is an efficient searching method and is one of the topics frequently asked in coding tests.
    \n    Through the above problem, I hope you have understood the principles and implementation methods of binary search,
    \n    and gained useful experience in writing code in Swift.\n<\/p>\n
    7. Additional Practice Problems<\/h2>\n
    \n    To deepen your understanding of binary search, try solving the additional problems below.\n<\/p>\n