704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Thoughts

• I mean, this is just a binary search....... idk that I have many other thoughts on this :sob:

Solution

class Solution {
    public int search(int[] nums, int target) {
        // Declare variables
        int h = nums.length - 1, l = 0;

        while (l <= h) {
            // Calculate the midpoint given the previous highs and lows
            int curIndex = ((h - l) / 2) + l;

            if (nums[curIndex] == target) {
                return curIndex;
            }

            // Set the highs and lows, excludes half of the data at a time for each iteration
            if (nums[curIndex] > target) {
                h = curIndex - 1;
            } else {
                l = curIndex + 1;
            }
        }

        return -1;
    }
}

Time Complexity: O(log n)
Space Complexity: O(1)

Conclusion

This one took me embarrassingly long to get. It has been a long time since I have had to use binary search, so it took me a while to remember how to do it. (Clearly I should've done more thinking about the question before I actually started!) Now that I have refreshed on it though, I feel way better about my understanding of it now, so perhaps this wasn't a complete wash.