Binary Search

Share

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Constraints:

Contents

Solution 1 - Using binary search

In this approach, we will apply Binary Search algorithm, since the input array is sorted in ascending order, we will use two pointers left and right to point to left and right end of array, and then using a while loop, compute the middle index mid = left + right _____________ 2 , then check if the element at mid index, based on the element found at mid index, we can draw three conclusions.

  • If the element at mid index is the target, then return the mid index.
  • If the element at mid index is greater than target, since the array is sorted in ascending order, this means that the target lies on left half of the array, so we will update right index to mid-1.
  • If the element at mid index is less than target, since the array is sorted in ascending order, this means that the target lies on right half of the array, so we will update left index to mid+1.

If that target is not found, we will return -1.

Java
public class BinarySearch {

    static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1;
        while(left <= right) {
            int mid = left + (right - left)/2; // to avoid integer overflow
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid]>target) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(search(new int[]{-1,0,3,5,9,12}, 9));
        System.out.println(search(new int[]{-1,0,3,5,9,12}, 2));
    }
}
Complexity Analysis:

Time complexity: Above code runs in O(log n) time where n is the length of input array nums.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code