Binary Search Algorithm in Java

Given an array of sorted integers and a target, find the index of the target in the array, if not found, return -1. 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.

Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

You can do a linear search from the beginning of the sorted array but that gives you O(N) complexity i.e. as in worst case, it requires N steps to iterate the array e.g. if the element is not found in the array.

Binary search narrows down the search domain to half every iteration, which improves the runtime complexity to O(logN). The Binary search to locate the target in a sorted array nums in Java is implemented below:

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int search(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (nums[mid] > target) {
                j = mid - 1;
            } else if (nums[mid] < target) {
                i = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (nums[mid] > target) {
                j = mid - 1;
            } else if (nums[mid] < target) {
                i = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

See other Binary Search algorithms:

• The Binary Search in Java
• GoLang: Binary Search Algorithm

–EOF (The Ultimate Computing & Technology Blog) —