Problem Statement (Easy)

  • Given an array of integers nums which is sorted in ascending order, and an integer target.
    Input: nums = [-1,0,3,5,9,12]
  • write a function to search target in nums.
    target = 9
  • If target exists, then return its index. Otherwise, return -1.
    Output: 4
    Explanation: 9 exists in nums and its index is 4

Example

    Input: nums = [-1,0,3,5,9,12], target = 2
    Output: -1
    Explanation: 2 does not exist in nums so return -1
    int [] numArray1 = { 4, 8, 9, 21, 32}; // length = 5 , mid element  = 9
    int [] numArray2 = { 4, 8, 9, 21, 32, 65 }; // length = 6, mid element = 9
Steps

    package com.naresh.algorithms;

    public class Problem704_binarySearch {

        // Binary Search time: O(logn) space: O(1)
        public static int search(int[] nums, int target) {
            int length = nums.length;
            int left = 0;
            int right = length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] == target) {
                    return mid;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            return -1;
        }

        public static void main(String[] args) {
            System.out.println("4 ?= " + search(new int[]{-1, 0, 3, 5, 9, 12}, 9));
            System.out.println("-1 ?= " + search(new int[]{-1, 0, 3, 5, 9, 12}, 2));
            System.out.println("0 ?= " + search(new int[]{5}, 5));
        }
    }

Reference