Java | Binary Search | Simple | 0-Based-Indexing
\n# Code\n\npackage LeetCode.Contest.Weekly_386_25022024;\n\nimport java.util.ArrayList;\nimport java.util.Arrays;\nimport java.util.HashMap;\nimport java.util.
\n# Code\n```\npackage LeetCode.Contest.Weekly_386_25022024;\n\nimport java.util.ArrayList;\nimport java.util.Arrays;\nimport java.util.HashMap;\nimport java.util.Scanner;\n\n\n/**\n * \n * Concept :- Binary Search .\n * Learning :- How to Implement the Binary search when Data is given According to 1-Based Indexing.\n * \n * Intution :- Before Implementing Binary search , You have to think that..\n *            1. Time is Montonously Increasing if mid is ok ... then mid+1, mid+2,.. all will satisfy.(we will move left).\n *            2. If mid is Not satisy nid-1, mid-2 will also not satisy. (we will Move right).\n *            3. Now convert the Whole qn in 0-Based Indexing that is More Good.\n *            4. Now Remember that high will be our ans.\n *            5. You can Keep high as Infinity as well upto Int_max.. But we are keeping m+1\n *            6. So if midvalue will satisfy then high == mid and high will be ans or move left.\n *            7. If mid is not satisfying then move left to mid+1.\n *            8. If mid is m+1 then it can\'t be ans.\n *            9. Ans range id [1...m].\n *            \n *          \n *          \n *   Time Complexity :-  O(NlogM)  ~ In worst Case.\n *   Space Complexity :- O(NlogM)  ~ logM times N space is Used.\n * \n * **/\n\npublic class Q3{\n    public static boolean BinarySearch(int[]nums, int[]changeIndexes , int seconds){\n        \n        int[]last = new int[nums.length];\n        Arrays.fill(last, -1);\n\n        for(int i=0; i<seconds; i++){\n            last[changeIndexes[i]-1] = i;\n        }\n\n\n        int marked = 0;\n        int oprn = 0;\n\n        for(int i=0; i< seconds; i++){\n\n            if(i == last[changeIndexes[i]-1]){\n\n                if(nums[changeIndexes[i]-1] > oprn)return false;\n                else{\n                    oprn-=nums[changeIndexes[i]-1];\n                    marked++;\n                }\n            }\n\n            else oprn++;\n        }\n        return marked == nums.length;\n    }\n    public static void main(String[] args) {\n\n        Scanner sc = new Scanner(System.in);\n\n        int n = sc.nextInt();\n        int m = sc.nextInt();\n\n        int[]nums = new int[n];\n        int[]changeIndexes = new int[m];\n\n        for(int i=0; i<n; i++)nums[i]=sc.nextInt();\n        for(int i=0; i<m; i++)changeIndexes[i]=sc.nextInt();\n\n        int low = 0;\n        int high= m+1;\n\n        while (low < high){\n\n            int mid = (low + high)/2;\n\n            if(BinarySearch(nums, changeIndexes , mid) == true){\n\n                high = mid;\n            }\n\n            else {\n\n                low = mid+1;\n            }\n        }\n\n        if(high==m+1) System.out.println(-1);\n        else System.out.println(high);\n\n    }\n}\n\n```
['Binary Search', 'Java']