LeetCode - Algorithms - 704. Binary Search

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky … — Donald Knuth

in the history in Section 6.2.1 of his Sorting and Searching, Knuth points out that while the first binary search was published in 1946, the first published binary search without bugs did not appear untial 1962. – Programming Pearls, Jon Bentley

Problem

704. Binary Search

Java

1

Copyright © 2000–2019 Robert Sedgewick and Kevin Wayne. All rights reserved.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int search(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (target < nums[mid])
                hi = mid - 1;
            else if (target > nums[mid])
                lo = mid + 1;
            else
                return mid;
        }
        return -1;        
    }
}

Submission Detail

  • 46 / 46 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Search.
  • Memory Usage: 40.6 MB, less than 29.73% of Java online submissions for Binary Search.

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int search(int[] nums, int target) {
        final int len = nums.length;
        int left=0, right=len-1;
        while(left<=right) {
            int mid = (left+right)/2;
            if (nums[mid]>target) {
                right = mid-1;
            }
            else if (nums[mid]<target){
                left = mid+1;
            }
            else {
                return mid;
            }
        }
        return -1;        
    }
}

Submission Detail

  • 46 / 46 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Search.
  • Memory Usage: 42.8 MB, less than 5.41% of Java online submissions for Binary Search.

ref