Java Coding Test Course, Finding Desired Integer

Hello! Today we will discuss one of the Java algorithm problems called “Finding the Desired Integer.” This problem will help you understand basic search algorithms that can be applied in various situations. I hope this article can contribute to enhancing your coding skills.

Problem Description

Given an integer array nums and a target integer target, the problem is to check if target exists in the array and return the index of that number if it exists. If it does not exist, it should return -1.

Input

• nums: integer array (e.g., [2, 7, 11, 15])
• target: the integer to be found (e.g., 9)

Output

• The index of target in the integer array, or -1 if it does not exist

Examples

Problem Solving Approach

There are several approaches to solving this problem, but the most basic method is to iterate through the array to find the target element. However, this method has a time complexity of O(n) and cannot use Binary Search if the elements are not sorted. So, what if the array is sorted? In that case, we can utilize binary search.

Binary Search Concept

Binary search is an efficient algorithm for finding the desired value in a sorted array. Here are the basic steps of binary search:

1. Calculate the middle index of the array.
2. If the middle value equals target, return that index.
3. If target is smaller than the middle value, search the left half of the array; if larger, search the right half.
4. Repeat this process.

Java Implementation

Now, let’s implement binary search in Java. Below is the code representation of the algorithm.

public class Solution {
        public int search(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;

            while (left <= right) {
                int mid = left + (right - left) / 2;

                if (nums[mid] == target) {
                    return mid; // found the target
                } else if (nums[mid] < target) {
                    left = mid + 1; // search in the right half
                } else {
                    right = mid - 1; // search in the left half
                }
            }
            return -1; // not found
        }
    }
    

Code Explanation

In the code above, the search method takes two arguments: the nums array and target. The method performs the following steps:

• Uses left and right variables to manage the range of search.
• The main loop continues searching as long as left is less than or equal to right.
• Calculates the middle index mid and returns that index if the middle value equals target.
• If the middle value is less than target, adjusts the left range; if more, adjusts the right range.
• If the search ends and target is not found, returns -1.

Complexity Analysis

The time complexity of the binary search algorithm is O(log n). This is because the range to search is halved each time the size of the array doubles. This algorithm is very fast and its efficiency stands out, especially in large arrays. The space complexity is O(1) as no additional space is needed.

Conclusion

In this article, we covered the Java algorithm problem of finding a desired integer. Through this problem, you could understand and implement binary search, which is fundamental to array searching. Since binary search is frequently featured in coding tests, I recommend practicing enough on this topic. Why not write your own code for various cases?

Finally, don’t forget to keep solving problems to improve your coding abilities! If you have any questions, feel free to ask in the comments. Thank you!