[javaSE] 数组（查找-二分查找）
前提数组必须是有序的
定义最小，最大，中间的角标索引
int min,max,mid;
min=0;
max=arr.length-1;
mid=(min+max)/2;上面的索引需要变化，使用循环，条件：当中间值不等于目标值时
int min,max,mid;
min=0;
max=arr.length-1;
mid=(min+max)/2;
while(arr[mid]!=key){
if(key<arr[mid]){
}else if(arr[mid]<key){
}
}当中间值大于目标值时，最大角标移动到中间角标-1位置
当中间值小于目标值时，最小角标移动到中间角标+1位置
中间角标继续二分
int min,max,mid;
min=0;
max=arr.length-1;
mid=(min+max)/2;
while(arr[mid]!=key){
if(key<arr[mid]){
max=mid-1;
}else if(arr[mid]<key){
min=mid+1;
}
mid=(min+max)/2;
}
return mid;此时的代码有问题，当找不到目标时，会陷入死循环，加一个判断
如果一直找不到，最小角标和最大角标会错位
int min,max,mid;
min=0;
max=arr.length-1;
mid=(min+max)/2;
while(arr[mid]!=key){
if(key<arr[mid]){
max=mid-1;
}else if(arr[mid]<key){
min=mid+1;
}
if(min>max) return -1;
mid=(min+max)/2;
}
return mid;java版：
public class ArrayDemo {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr=new int[]{1,4,6,7,8,9};
System.out.println("索引:"+keySearch(arr,7));//索引:3
System.out.println("索引:"+helfSearch(arr,7));//索引:3
}
/**
* 二分查找
* @param arr
* @param key
* @return
*/
public static int helfSearch(int[] arr,int key){
int min,max,mid;
min=0;
max=arr.length-1;
mid=(min+max)/2;
while(arr[mid]!=key){
if(key<arr[mid]){
max=mid-1;
}else if(arr[mid]<key){
min=mid+1;
}
if(min>max) return -1;
mid=(min+max)/2;
}
return mid;
}
/**
* 获取该值在数组中第一次出现的位置
* @param arr
* @param num
* @return
*/
public static int keySearch(int[] arr,int num){
for(int i=0;i<arr.length;i++){
if(arr[i]==num){
return i;
}
}
return -1;
}
}PHP版：
<?php
class ArrayDemo{
public static function main(){
$arr=array(1,4,6,7,8,9);
echo "索引:".ArrayDemo::keySearch($arr,7);//索引:3
echo "索引:".ArrayDemo::helfSearch($arr,7);//索引:3
}
/**
* 二分查找
* @param arr
* @param key
* @return
*/
public static function helfSearch($arr,$key){
$min=0;
$max=count($arr)-1;
$mid=ceil(($min+$max)/2);
while($arr[$mid]!=$key){
if($key<$arr[$mid]){
$max=$mid-1;
}else if($arr[$mid]<$key){
$min=$mid+1;
}
$mid=ceil(($min+$max)/2);
if($min>$max) return -1;
}
return $mid;
}
/**
* 获取该值在数组中第一次出现的位置
* @param arr
* @param num
* @return
*/
public static function keySearch($arr,$key){
for($i=0;$i<count($arr);$i++){
if($arr[$i]==$key){
return $i;
}
}
return -1;
}
}
ArrayDemo::main();本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-05-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读