Binary Search

• Understanding binary search
• Solved problems are presented in alphabetical order

Problems related to binary search

Binary Search

↗ See LeetCode Problem #704

Java

public class Solution {    static int search(int[] nums, int target) {        int pivot;        int left = 0;        int right = nums.length - 1;        while (left <= right) {            pivot = left + (right - left) / 2;            if (nums[pivot] == target) {                return pivot;            }            if (target < nums[pivot]) {                right = pivot - 1;            } else {                left = pivot + 1;            }        }        return -1;    }    public static void main(String[] args) {        // Example 1:        int[] nums1 = {-1,0,3,5,9,12};        int target1 = 9;        //  O/P: 4        // Example 2:        int[] nums2 = {-1,0,3,5,9,12};        int target2 = 2;        //  O/P: -1        System.out.println(search(nums1, target1));        System.out.println(search(nums2, target2));    }}

First Bad Version

↗ See LeetCode Problem #278

Java

//  To make it work outside the LeetCode environment://  Requires the CORRECT implementation of VersionControl class//      with boolean isBadVersion(int version) method/API//  INCORRECT Implementation//      so that my IDE doesn't yell at me!!!class VersionControl {    static boolean isBadVersion (int n) {        return true;    }}public class Solution extends VersionControl {    static int firstBadVersion(int n) {        int leftIndex = 1;        int rightIndex = n;        while (leftIndex <= rightIndex) {            int pivotIndex = leftIndex + (rightIndex - leftIndex) / 2;            //  Not bad version            if (!isBadVersion (pivotIndex)) {                //  First bad version should be                //      on the right side of the pivotIndex                leftIndex = pivotIndex + 1;            //  Bad version            } else {                //  First bad version should be                //      on the left side of the pivotIndex                //  Meaning, pivotIndex < current pivotIndex                rightIndex = pivotIndex - 1;            }        }        return leftIndex;    }    public static void main(String[] args) {        // Example 1:        int n1 = 5;        int bad1 = 4;        //  O/P: 4        // Example 2:        int n2 = 1;        int bad2 = 1;        //  O/P: 1        System.out.println(firstBadVersion(n1));        System.out.println(firstBadVersion(n2));    }}

Maximum Profit in Job Scheduling

↗ See LeetCode Problem #1235

Java

import java.util.List;import java.util.ArrayList;import java.util.Queue;import java.util.PriorityQueue;import java.util.Comparator;public class Solution {    static class ArrayComparator implements Comparator <ArrayList<Integer>> {        public int compare (ArrayList<Integer> aList1,                            ArrayList<Integer> aList2) {            return aList1.get(0) - aList2.get(0);        }    }    private static int findMaxProfit (List<List<Integer>> jobsList) {        //  Initialize maximum profit        int maxProfit = 0;        //  Declare a minimum heap with PriorityQueue        //      using ArrayComparator to set priority        //  Each entry will have end time and profit only        Queue<ArrayList<Integer>> minHeap =                new PriorityQueue<>(new ArrayComparator());        for (int i = 0; i < jobsList.size(); i++) {            int startTime = jobsList.get(i).get(0);            int endTime = jobsList.get(i).get(1);            int profit = jobsList.get(i).get(2);            //  Check until minHeap is not empty            //      and update the maxProfit            while (!minHeap.isEmpty() &&                    startTime >= minHeap.peek().get(0)) {                maxProfit = Math.max(maxProfit, minHeap.peek().get(1));                minHeap.poll();            }            //  Declare an ArrayList for the updated combined job            ArrayList<Integer> updatedJob = new ArrayList<>();            //  Add the current end time            updatedJob.add(endTime);            //  Add the updated maximum profit            updatedJob.add(profit + maxProfit);            //  Update minHeap            minHeap.offer(updatedJob);        }        while (!minHeap.isEmpty()) {           maxProfit = Math.max(maxProfit, minHeap.peek().get(1));           minHeap.poll();        }        return maxProfit;    }    public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {        List<List<Integer>> jobsList = new ArrayList<>();        for (int i = 0; i < profit.length; i++) {            List<Integer> currentJob = new ArrayList<>();            currentJob.add(startTime[i]);            currentJob.add(endTime[i]);            currentJob.add(profit[i]);            jobsList.add(currentJob);        }        //  Sort JobsList by the start time of each job        jobsList.sort(Comparator.comparingInt(a -> a.get(0)));        return findMaxProfit(jobsList);    }    public static void main(String[] args) {        // Example 1:        int[] startTime1 = {1,2,3,3};        int[] endTime1 = {3,4,5,6};        int[] profit1 = {50,10,40,70};        //  O/P: 120        // Example 2:        int[] startTime2 = {1,2,3,4,6};        int[] endTime2 = {3,5,10,6,9};        int[] profit2 = {20,20,100,70, 60};        //  O/P: 150        // Example 3:        int[] startTime3 = {1,1,1};        int[] endTime3 = {2,3,4};        int[] profit3 = {5,6,4};        //  O/P: 6        System.out.println(jobScheduling(startTime1, endTime1, profit1));        System.out.println(jobScheduling(startTime2, endTime2, profit2));        System.out.println(jobScheduling(startTime3, endTime3, profit3));    }}

Median of Two Sorted Arrays

↗ See LeetCode Problem #4

Java

public class Solution {    static double findMedianSortedArrays(int[] nums1, int[] nums2) {        if (nums1.length > nums2.length) {            return findMedianSortedArrays(nums2, nums1);        }        int[] a = nums1;        int[] b = nums2;        int aLength = a.length;        int bLength = b.length;        // range of a1 cut location: n1 means no right half for a1        int l = 0, r = aLength;        while (l <= r) {            int cut1 = (l + r) / 2; // cut location is counted to right half            int cut2 = (aLength + bLength + 1) / 2 - cut1;            int l1 = cut1 == 0 ? Integer.MIN_VALUE : a[cut1 - 1];            int l2 = cut2 == 0 ? Integer.MIN_VALUE : b[cut2 - 1];            int r1 = cut1 == aLength ? Integer.MAX_VALUE : a[cut1];            int r2 = cut2 == bLength ? Integer.MAX_VALUE : b[cut2];            if (l1 <= r2 && l2 <= r1) {                if ((aLength + bLength) % 2 == 0) {                    return ((double) Math.max(l1, l2) + Math.min(r1, r2)) / 2;                } else {                    return (double) Math.max(l1, l2);                }            } else if (l1 > r2) {                r = cut1 - 1;            } else {                l = cut1 + 1;            }        }        throw new IllegalArgumentException();    }    public static void main(String[] args) {        // Example 1:        int[] numsA1 = {1,3};        int[] numsA2 = {2};        //  O/P: 2.00000        // Example 2:        int[] numsB1 = {1,2};        int[] numsB2 = {3,4};        //  O/P: 2.50000        System.out.println(findMedianSortedArrays(numsA1, numsA2));        System.out.println(findMedianSortedArrays(numsB1, numsB2));    }}

Search in Rotated Sorted Array

↗ See LeetCode Problem #33

Java

public class Solution {    public static int search(int[] nums, int target) {        int startIndex = 0;        int endIndex = nums.length - 1;        while (startIndex <= endIndex) {            int middleIndex = startIndex + (endIndex - startIndex) / 2;            if (target == nums[middleIndex]) {                return middleIndex;            }            if (nums[startIndex] <= nums[middleIndex]) {                if (target >= nums[startIndex] && target < nums[middleIndex]) {                    endIndex = middleIndex - 1;                } else {                    startIndex = middleIndex + 1;                }            } else {                if (target < nums[startIndex] && target >= nums[middleIndex]) {                    startIndex = middleIndex + 1;                } else {                    endIndex = middleIndex - 1;                }            }        }        return -1;    }    public static void main (String[] args) {        // Example 1:        int[] nums1 = {4,5,6,7,0,1,2};        int target1 = 0;        //  O/P: 4        // Example 2:        int[] nums2 = {4,5,6,7,0,1,2};        int target2 = 3;        //  O/P: -1        // Example 3:        int[] nums3 = {1};        int target3 = 0;        //  O/P: -1        System.out.println(search(nums1,target1));        System.out.println(search(nums2,target2));        System.out.println(search(nums3,target3));    }}

Time Based Key Value Store

↗ See LeetCode Problem #981

Java

import java.util.Map;import java.util.HashMap;import java.util.TreeMap;public class TimeMap {    //  Declare timeMap for global use    private Map<String, TreeMap> timeMap;    public TimeMap() {        //  Initialize timeMap        timeMap = new HashMap<>();    }    public void set(String key, String value, int timestamp) {        //  If given key is not already in timeMap,        //      put key and a new tree map        if(!timeMap.containsKey(key)) {           timeMap.put(key, new TreeMap<>());        }        //  First get the value for the given key:        //      a TreeMap        //  Put timestamp as key and value as value in the TreeMap        timeMap.get(key).put(timestamp, value);    }    public String get(String key, int timestamp) {        //  Get the value (as TreeMap) for a given key        //      from the TimeMap, and        //      store it newly declared treeMap        TreeMap<Integer, String> treeMap = timeMap.get(key);        //  If treeMap is null, return an empty string        if (treeMap == null) {            return "";        }        //  Returns the greatest key less than or equal to        //      the given key, or null if there is no such key.        //  Declare an integer to store the greatest key (timestamp here)        //      less than or equal to the given key        Integer floorTimestamp = treeMap.floorKey(timestamp);        //  If floorTimestamp is null, return an empty string        if (floorTimestamp == null) {            return "";        }        //  Return the value from treeMap corresponding        //      to the greatest key (timestamp here)        //      less than or equal to the given key        return treeMap.get(floorTimestamp);    }    public static void main(String[] args) {        // Example 1:        //Input        //["TimeMap", "set", "get", "get", "set", "get", "get"]        //[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4]        //, ["foo", 5]]        TimeMap timeMap = new TimeMap();        timeMap.set("foo", "bar", 1);//        timeMap.get("foo", 1);        System.out.println(timeMap.get("foo", 1));//        timeMap.get("foo", 3);        System.out.println(timeMap.get("foo", 3));        timeMap.set("foo", "bar2", 4);//        timeMap.get("foo", 4);        System.out.println(timeMap.get("foo", 4));//        timeMap.get("foo", 5);        System.out.println(timeMap.get("foo", 5));        //  O/P:        //[null, null, "bar", "bar", null, "bar2", "bar2"]    }}