Binary Search in Java

It is Thursday and not much to report. My wife and I are planning on baking a couple things this weekend. Will update you on a couple recipes we are interested in making.

Earlier today I selected LeetCode 704 Binary Search. I was browsing the LeetCode site and have not implemented the binary search algorithm in this blog so here it is.

Given a sorted (in ascending order) integer array nums of n elements 
and a target value, 
write a function to search target in nums. 
If target exists, then return its index, otherwise return -1.

Note:

o You may assume that all elements in nums are unique.
o n will be in the range [1, 10000].
o The value of each element in nums will be in the range [-9999, 9999].

The array need to have numbers in sorted order. If the numbers are not sorted it is easy to figure out that it will not work. The opposite is true for a binary reach tree. If the input is sorted we will get an inefficient linked list with all the values.

In the requirements we are told to search for a target value and return the index in the array. If we do not find the target value we should return a -1. This is a good way to be able to include the whole set of integers as data.

As usual, if you are interested in the problem please visit the LeetCode website and get the requirements and examples from the source. I am not sure if with time things change. That said; it is important to take into account the notes. Having duplicates may complicate things to the point that the algorithm might not work. Not sure what the other two notes imply. Perhaps there is some type of optimization we could achieve is we take advantage of them.

I will be developing the solution using the Java programming language in a Windows 10 machine and using the VSCode IDE. Since the solution is in Java it should run on any platform supporting the language. Your choice of OS and IDE is up to you and should be irrelevant. When I have a candidate that should work, I copy the code into the IDE provided by LeetCode and run it.

class Solution {
    public int search(int[] nums, int target) {
        
    }
}

Based on the requirements the signature for the function / method we need to develop makes sense. Given a sorted array of integers look for the target and return the associated index.

-1,0,3,5,9,12
9
main <<<    arr: [-1, 0, 3, 5, 9, 12]
main <<< target: 9
main <<< output: 4


-1,0,3,5,9,12
2
main <<<    arr: [-1, 0, 3, 5, 9, 12]
main <<< target: 2
main <<< output: -1


6
6
main <<<    arr: [6]
main <<< target: 6
main <<< output: 0


5
6
main <<<    arr: [5]
main <<< target: 6
main <<< output: -1


-1,0,3,5,9,12,13
9
main <<<    arr: [-1, 0, 3, 5, 9, 12, 13]
main <<< target: 9
main <<< output: 4


-1,0,3,5,9,12,13
3
main <<<    arr: [-1, 0, 3, 5, 9, 12, 13]
main <<< target: 3
main <<< output: 2


2,3,4,10,20 
10
main <<<    arr: [2, 3, 4, 10, 40]
main <<< target: 10
main <<< output: 3

I believe two of the test cases came from LeetCode. The others I put together to make sure things were working as expected.

It seems that we input a line of sorted integers and a line with the target. Our test program should read the two input lines, prepare the array and the target arguments for the search() function / method we will implement. In addition our test code should make a call to the function and display the result.

Please note that if you implement your code directly on the LeetCode site, you will not require the test scaffolding code.

    /**
     * Test scaffolding.
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {

        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // **** read line with array values ****
        String[] strArr = br.readLine().trim().split(",");

        // **** read line with target ****
        int target = Integer.parseInt(br.readLine().trim());

        // **** close buffered reader ****
        br.close();
        
        // **** create and populate integer array ****
        int[] arr = Arrays.stream(strArr).mapToInt(Integer::parseInt).toArray();

        // ???? ????
        System.out.println("main <<<    arr: " + Arrays.toString(arr));
        System.out.println("main <<< target: " + target);

        // **** search array for target, return index, and display result ****
        System.out.println("main <<< output: " + search(arr, target));
    }

We start by opening a buffered reader and reading the two input lines. We then close the buffered reader. Next we generate an array of integers from the string array we generated when we read the first input line. The two arguments for our function / method are displayed to make sure all is well so far. We then call the function in question, collect and display the result. It seems that the code is as expected and matches what we saw on the screen captures executing the tests.

    /**
     * Search for target in nums.
     * Entry point for recursion.
     */
    static int search(int[] nums, int target) {

        // **** sanity checks ****
        if (nums.length == 1) {
            if (nums[0] == target)
                return 0;
            else
                return -1;
        }

        // **** start recursion ****
        int index = search(nums, target, 0, nums.length - 1);

        // **** return index of target in array ****
        return index;
    }

We will pass a couple arguments to the function and will make it recursive. For this reason we will make this an entry point for the recursive call. We start with a sanity check. I like to do so in order to reduce execution time and possibly take care of end conditions. We then start recursion with two additional arguments. The third argument is the left index and the fourth the right index for the search. In other words we need to start by looking at the entire array of integers. When all is said and done we return the index of the target. Note that it could be -1 if the target was not found.

    /**
     * Recursive function / method O(log(n))
     * Runtime: 0 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 40.2 MB, less than 22.21% of Java online submissions.
     */
    static int search(int[] arr, int target, int left, int right) {

        // **** base case ****
        if (left > right)
            return -1;

        // **** compute mid point ****
        int mid = left + (right - left) / 2;

        // **** check if we found the target ****
        if (arr[mid] == target)
            return mid;

        // **** decide which way to go ****
        if (target > arr[mid]) {
            left = mid + 1;                 // go right
        } else {
            right = mid - 1;                // go left
        }

        // **** recurse ****
        return search(arr, target, left, right);
    }

This function implements the core of the algorithm. For recursion we need so form of base case to end the process. In this case when the left index is greater than the right index, we are done and we did not find the target value.

We then compute the midpoint within the left and right values. We then check if the target was found. If so we return the value for the mid index we just computed.

The next step is to decide if we are going towards the left or right in the array. If the target is larger than the midpoint value, we need to search the right side of the array; otherwise we need to continue the search in the left side of the array.

At this point we are ready to continue recursion to search for the target in the smaller array defined by left and right indices.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.

One last thing, many thanks to all 5,067 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

Regards;

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.