Likou 704 - binary search

Title description

Given an n-element sorted (ascending) integer array nums and a target value target , write a function to search for target in nums and return the subscript if the target value exists, otherwise return -1.

Solution ideas

• This is a simple question. Since the question is given in an ordered array, the binary search method can be used to find elements;

• Ascending order and descending order are only partially different when judging boundary conditions;

• To find the middle element, you can directly write int mid = (left + right) / 2;

• But writing this way, when the size of the array is large, it is easy to cause integer data overflow;

• So consider using bitwise operations int mid=left + ((right - left) >> 1);

• The interval used is the left and right closed interval [left, right], which I think is better understood.

Input and output example

Code

class Solution {public int search(int[] nums, int target) {int n = nums.length;if(target < nums[0] || target > nums[n - 1]) return -1;int left = 0, right = n - 1;while(left <= right){//int mid = left + ((right - left) >> 1); // this is written to prevent overflow of out-of-integer dataint mid = (left + right) / 2;if(target > nums[mid]){left = mid + 1;}else if(target < nums[mid]){right = mid - 1;}else return mid;}return -1;}}