LeetCode - Easy - 704. Binary Search

谁践踏了优雅 2022-11-17 03:51 109阅读 0赞

## Topic ##

*  Binary Search

## Description ##

[https://leetcode.com/problems/binary-search/][https_leetcode.com_problems_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.

**Example 1:**

Input: nums = [-1,0,3,5,9,12], target = 9
    Output: 4
    Explanation: 9 exists in nums and its index is 4

**Example 2:**

Input: nums = [-1,0,3,5,9,12], target = 2
    Output: -1
    Explanation: 2 does not exist in nums so return -1

**Constraints:**

*   1 < = n u m s . l e n g t h < = 1 0 4 1 <= nums.length <= 10^4 1<=nums.length<=104
 *   − 9999 < = n u m s \[ i \] , t a r g e t < = 9999 -9999 <= nums\[i\], target <= 9999 −9999<=nums\[i\],target<=9999
 *  All the integers in **nums** are unique.
 *  **nums** is sorted in an ascending order.

## Analysis ##

![bd9cfb80cb63d8290c35d3717660dfaa.gif][]

## Submission ##

public class BinarySearch { 
    	public int search(int[] nums, int target) { 
    		int left = 0, right = nums.length - 1, mid;
    
    		while (left <= right) { 
    			mid = left + (right - left) / 2;
    
    			if (nums[mid] < target) { 
    				left = mid + 1;
    			} else if (nums[mid] > target) { 
    				right = mid - 1;
    			} else { 
    				return mid;
    			}
    		}
    		return -1;
    	}
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class BinarySearchTest { 
    
    	@Test
    	public void test() { 
    		BinarySearch obj = new BinarySearch();
    
    		assertEquals(4, obj.search(new int[] {  -1, 0, 3, 5, 9, 12 }, 9));
    		assertEquals(-1, obj.search(new int[] {  -1, 0, 3, 5, 9, 12 }, 2));
    		assertEquals(0, obj.search(new int[] { 5}, 5));
    	}
    }

[https_leetcode.com_problems_binary-search]: https://leetcode.com/problems/binary-search/
[bd9cfb80cb63d8290c35d3717660dfaa.gif]: /images/20221022/7576713018184264a6e1e8b900e2a907.png