{"id":33458,"date":"2024-11-01T09:16:45","date_gmt":"2024-11-01T09:16:45","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33458"},"modified":"2024-11-01T11:38:36","modified_gmt":"2024-11-01T11:38:36","slug":"java-coding-test-course-binary-search","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33458\/","title":{"rendered":"Java Coding Test Course, Binary Search"},"content":{"rendered":"

<\/p>\n

\n
\n

Author: [Your Name]<\/p>\n

Date: [Date]<\/p>\n<\/header>\n

\n

1. Introduction to Binary Search Algorithm<\/h2>\n

Binary Search is an algorithm used to find a specific value in a sorted array. It is implemented by comparing the middle value of the array; if the desired value is less than the middle value, it searches in the left part; if greater, it searches in the right part. Binary Search is highly efficient with a time complexity of O(log n).<\/p>\n

To use Binary Search, the array must be sorted; otherwise, a different search method, Linear Search, should be used.<\/p>\n<\/section>\n

\n

2. Example Problem of Binary Search<\/h2>\n

Problem: Find the Index of a Specific Value<\/h3>\n

Given a sorted array of integers nums<\/code> and an integer target<\/code>, write a function binarySearch<\/code> that returns the index of target<\/code>. If target<\/code> does not exist, it should return -1<\/code>.<\/p>\n

Example Input<\/h3>\n
\nnums = [1, 2, 3, 4, 5, 6, 7, 8, 9]\ntarget = 5\n            <\/pre>\n
Example Output<\/h3>\n
\n4\n            <\/pre>\n<\/section>\n
\n
3. Problem Solving Process<\/h2>\n
3.1 Problem Analysis<\/h3>\n
The task is to find the index of target<\/code> in the given nums<\/code> array, so it is essential to utilize the fact that the array is sorted. The search will be performed by calculating the middle value and narrowing the search range through comparisons with target<\/code>.<\/p>\n
3.2 Algorithm Design<\/h3>\n
The Binary Search algorithm includes the following steps:<\/p>\n
    \n
  1. Initialize the starting index left<\/code> and ending index right<\/code> of the array.<\/li>\n
  2. Calculate the middle index mid<\/code>: mid = (left + right) \/ 2<\/code>.<\/li>\n
  3. Compare the middle value nums[mid]<\/code> with target<\/code>.<\/li>\n
  4. If the middle value is equal to target<\/code>, return mid<\/code>.<\/li>\n
  5. If the middle value is less than target<\/code>, update left = mid + 1<\/code>; otherwise, update right = mid - 1<\/code>.<\/li>\n
  6. Repeat this process until left<\/code> is greater than right<\/code>.<\/li>\n
  7. If it decreases, return -1<\/code> indicating that target<\/code> is not in the array.<\/li>\n<\/ol>\n
    3.3 Java Code Implementation<\/h3>\n
    Let\u2019s implement the above algorithm in Java.<\/p>\n
    \n\npublic class BinarySearch {\n    public static int binarySearch(int[] nums, int target) {\n        int left = 0;\n        int right = nums.length - 1;\n\n        while (left <= right) {\n            int mid = left + (right - left) \/ 2;\n\n            if (nums[mid] == target) {\n                return mid; \/\/ Return index if found\n            } else if (nums[mid] < target) {\n                left = mid + 1; \/\/ Search right\n            } else {\n                right = mid - 1; \/\/ Search left\n            }\n        }\n\n        return -1; \/\/ Return -1 if not found\n    }\n\n    public static void main(String[] args) {\n        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};\n        int target = 5;\n        int result = binarySearch(nums, target);\n        System.out.println(result);\n    }\n}\n<\/code>\n            <\/pre>\n<\/section>\n
    \n
    4. Time Complexity Analysis<\/h2>\n
    The time complexity of the Binary Search algorithm is O(log n). This is because the size of the array reduces by half with each search. Therefore, Binary Search performs better with larger amounts of data.<\/p>\n<\/section>\n
    \n
    5. Conclusion<\/h2>\n
    In this lecture, we explored the concept of Binary Search and problems utilizing it. Binary Search is an efficient searching method for sorted arrays and is a basic algorithm frequently featured in various coding tests. As preparation for actual coding tests, practice solving various Binary Search problems to assess your skills.<\/p>\n<\/section>\n