Java Coding Test Course, Binary Search

Author: [Your Name]

Date: [Date]

1. Introduction to Binary Search Algorithm

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).

To use Binary Search, the array must be sorted; otherwise, a different search method, Linear Search, should be used.

2. Example Problem of Binary Search

Problem: Find the Index of a Specific Value

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

Example Input

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5

Example Output

4

3. Problem Solving Process

3.1 Problem Analysis

The task is to find the index of target in the given nums 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.

3.2 Algorithm Design

The Binary Search algorithm includes the following steps:

  1. Initialize the starting index left and ending index right of the array.
  2. Calculate the middle index mid: mid = (left + right) / 2.
  3. Compare the middle value nums[mid] with target.
  4. If the middle value is equal to target, return mid.
  5. If the middle value is less than target, update left = mid + 1; otherwise, update right = mid - 1.
  6. Repeat this process until left is greater than right.
  7. If it decreases, return -1 indicating that target is not in the array.

3.3 Java Code Implementation

Let’s implement the above algorithm in Java.


public class BinarySearch {
    public static int binarySearch(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; // Return index if found
            } else if (nums[mid] < target) {
                left = mid + 1; // Search right
            } else {
                right = mid - 1; // Search left
            }
        }

        return -1; // Return -1 if not found
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 5;
        int result = binarySearch(nums, target);
        System.out.println(result);
    }
}

4. Time Complexity Analysis

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.

5. Conclusion

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.

Thank you!