Binary Search

In this section, we will implement naive simple binary search here which utilised sorted array.

We need to define the function search as follow. This run in O(log(n)) time because it is always halved.

    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;

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

            if (nums[mid] > target ) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }

You can try to run the code here:
Run on jdoodle