Binary Search | Learn for Master
  • Leetcode – Search for a Range (Java)

    Search for a Range

    Given a sorted array of integers, find the starting and ending position of a given target value.

    Your algorithm’s runtime complexity must be in the order of O(log n).

    If the target is not found in the array, return [-1, -1].

    For example,
    Given [5, 7, 7, 8, 8, 10] and target value 8,
    return [3, 4].


    This problem is equivalent to find the lower bound and upper bound of the target value in the sorted array. 

    For instance, given a sorted array [1,

    [Read More...]
  • binary search – first bad version

    You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

    Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

    You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version.

    [Read More...]
  • LeetCode – Median of Two Sorted Arrays Java Solution

    There are two sorted arrays nums1 and nums2 of size m and n respectively.

    Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

    Example 1:

    Example 2:


    It is easy to come up with a O(n) solution. Then it is high likely that the interviewer will ask you to give the algorithm with time complexity O(logn). 

    For any problem with sorted array, to come up with a O(logN) solution, we should consider the binary search related algorithm. 

    [Read More...]
  • LeetCode- Search in Rotated Sorted Array

    Leetcode- search in rotated sorted array

    Suppose a sorted array is rotated at some pivot unknown to you beforehand.

      (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

      You are given a target value to search. If found in the array return its index, otherwise return -1.

      You may assume no duplicate exists in the array.

    Leetcode- search in rotated sorted array

    Using the idea of binary search, we can reduce the search space based on which range the target value is located. 

    We first get the mid index of the array,

    [Read More...]