Binary Search

Binary Search: 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

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

1 <= nums.length <= 10^4.
-10^4 < nums[i], target < 10^4
All the integers in nums are unique.
nums is sorted in ascending order.

Try this Problem on your own or check similar problems:

Solution:

Java
JavaScript
Python
C++

public int search(int[] nums, int target) {
    int low = 0, high = nums.length - 1;

    while(low <= high){
        int mid = low + (high-low)/2;
        if(nums[mid] == target){
            return mid;
        }
        else if(nums[mid] < target){
            low = mid + 1;
        }
        else{
            high = mid - 1;
        }
    }

    return -1;
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let low = 0,
    high = nums.length - 1;

  while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
};

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) - 1

        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1

        return -1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }

        return -1;
    }
};

Time/Space Complexity:

Time Complexity: O(log n)
Space Complexity: O(1)

Explanation:

This is a simple problem utilizing well known binary search. But the right implementation of binary search can be tricky, here are steps you should take when implementing binary search (or some modification of it):

Is there any total or implicit order (order as in sorted array), you first thought should be to utilize binary search.
Determine the low and high. In most cases low and high would represent the start and end of input array/list.
Define a loop invariant that will be true for the whole execution of the loop (in this case low <= high)
Calculate mid element. The only tip here is to use low + (high-low)/2 instead of (low + high)/2, we do this to prevent overflow (think of high being a big number and adding low to it would overflow the integer)
Eliminate elements (in most cases half of array). So, if we don’t find an element we have to check if the current element at mid position is either larger or smaller than the target. If it's smaller there is no point in searching in the left half (since the array is sorted and any element before mid will be also smaller than target). Same goes when the mid element is larger than the target, then we don't have to search for it in the right half. Since we're eliminating half array each iteration we get to O(log n) time complexity (in other words how many time can we half an array of n elements).

Example 1:​

Example 2:​

Example 3:​

Constraints:​

Solution:​

Time/Space Complexity:​