Binary Search: O(NlogN)

First Thoughts: low, med, high를 계속 keep track 하고 update 해줘야 겠다는 생각을 먼저 했다. 결국에는 med 값은 target과 같아질 수 밖에 없다. 만약 target 값을 거쳐가지 않았다면 배열에 target이 없다는 의미. control condition은 low 가 high 보다 낮거나 같다.

My Solution:

class Solution {
    public int search(int[] nums, int target) {
        int low = 0;
        int pivot = 0;
        int high = nums.length-1;
        while (low <= high) {
            pivot = (low+high) / 2;
            if (nums[pivot]==target) return pivot;
            if (target < nums[pivot]) high = pivot -1;
            else low = pivot + 1;
        }
        return -1;
    }
}

Catch Point

1. The 'pivot' or midpoint eventually passes the target (if it exists). The while loop goes on until low is less or equal to high point.