# Classical Binary Search

Easy

## Question

Find any position of a target number in a sorted array. Return -1 if target does not exist.

Example
Given [1, 2, 2, 4, 5, 5] .
For target = 2 , return 1 or 2.
For target = 5 , return 4 or 5.
For target = 6 , return -1.

O(logn) time

## Solution

``````public class Solution {
/**
* @param nums: An integer array sorted in ascending order
* @param target: An integer
* @return an integer
*/
public int findPosition(int[] nums, int target) {
// invalid input
if (nums == null || nums.length == 0) {
return -1;
}
// out of range
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
}
``````
``````public class Solution {
/**
* @param nums: An integer array sorted in ascending order
* @param target: An integer
* @return an integer
*/
public int findPosition(int[] nums, int target) {
// invaild input
if (nums == null || nums.length == 0) {
return -1;
}
// out of range
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start <= end) {
// avoid divid by zero error
if (nums[end] == nums[start] || start == end) {
if (nums[start] != target) {
return -1;
} else {
return start;
}
}
int mid = Math.min(end, start + (target / (nums[end] - nums[start])) / (end - start));
if (nums[mid] == target) {
return mid;
}
if (nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
}
``````