Interview 150
Binary Search
- Problem
- LC 704
- File
- interview150_LC704BinarySearch.java
- Path
- pkg5leetcode/interview150/interview150_LC704BinarySearch.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC704BinarySearch.java
- Approach
- Classic binary search on sorted array.
- Complexity
- Time O(log n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Binary Search | LC 7045 * APPROACH: Classic binary search on sorted array.6 * COMPLEXITY: Time O(log n), Space O(1)7 */8public class interview150_LC704BinarySearch {9 static int search(int[] nums, int target) {10 int lo = 0, hi = nums.length - 1;11 while (lo <= hi) {12 int mid = lo + (hi - lo) / 2;13 if (nums[mid] == target) return mid;14 if (nums[mid] < target) lo = mid + 1;15 else hi = mid - 1;16 }17 return -1;18 }19 20 public static void main(String[] args) {21 check(search(new int[]{-1, 0, 3, 5, 9, 12}, 9) == 4, "case1");22 check(search(new int[]{-1, 0, 3, 5, 9, 12}, 2) == -1, "case2");23 System.out.println("all tests passed");24 }25 26 static void check(boolean cond, String name) {27 if (!cond) throw new AssertionError("FAILED: " + name);28 System.out.println(" PASS " + name);29 }30}